## CryptoDB

### Jörn Müller-Quade

#### Publications

**Year**

**Venue**

**Title**

2021

ASIACRYPT

ConTra Corona: Contact Tracing against the Coronavirus by Bridging the Centralized–Decentralized Divide for Stronger Privacy
Abstract

Contact tracing is among the most important interventions to mitigate the spread of any pandemic usually in the form of manual contact tracing. Smartphone-facilitated digital contact tracing may help to increase tracing capabilities and extend the coverage to those contacts one does not know in person. Most implemented protocols use local Bluetooth Low Energy (BLE) communication to detect contagion-relevant proximity, together with cryptographic protections, as necessary to improve the privacy of the users of such a system. However, current decentralized protocols, including DP3T, do not sufficiently protect infected users from having their status revealed to their contacts, which raises fear of stigmatization.
We alleviate this by proposing a new and practical solution with stronger privacy guarantees against active adversaries. It is based on the upload-what-you-observed paradigm, includes a separation of duties on the server side, and a mechanism to ensure that users cannot deduce which encounter caused a warning with high time resolution. Finally, we present a simulation-based security notion of digital contact tracing in the real–ideal setting, and prove the security of our protocol in this framework.

2021

TCC

Environmentally Friendly Composable Multi-Party Computation in the Plain Model from Standard (Timed) Assumptions
Abstract

Starting with the work of Rivest et al. in 1996, timed assumptions have found many applications in cryptography, building e.g. the foundation of the blockchain technology. They also have been used in the context of classical MPC, e.g. to enable fairness. We follow this line of research to obtain composable general MPC in the plain model.
This approach comes with a major advantage regarding environmental friendliness, a property coined by Canetti et al. (FOCS 2013). Informally, this means that our constructions do not “hurt” game-based security properties of protocols that hold against polynomial-time adversaries when executed alone.
As an additional property, our constructions can be plugged into any UC-secure protocol without loss of security.
Towards proving the security of our constructions, we introduce a variant of the UC security notion that captures timed cryptographic assumptions. Combining standard timed commitment schemes and standard polynomial-time hardness assumptions, we construct a composable commitment scheme in the plain model. As this construction is constant-round and black-box, we obtain the first fully environmentally friendly composable constant-round black-box general MPC protocol in the plain model from standard (timed) assumptions.

2018

PKC

Reusing Tamper-Proof Hardware in UC-Secure Protocols
Abstract

Universally composable protocols provide security even in highly complex environments like the Internet. Without setup assumptions, however, UC-secure realizations of cryptographic tasks are impossible. Tamper-proof hardware tokens, e.g. smart cards and USB tokens, can be used for this purpose. Apart from the fact that they are widely available, they are also cheap to manufacture and well understood.Currently considered protocols, however, suffer from two major drawbacks that impede their practical realization:The functionality of the tokens is protocol-specific, i.e. each protocol requires a token functionality tailored to its need.Different protocols cannot reuse the same token even if they require the same functionality from the token, because this would render the protocols insecure in current models of tamper-proof hardware.
In this paper we address these problems. First and foremost, we propose formalizations of tamper-proof hardware as an untrusted and global setup assumption. Modeling the token as a global setup naturally allows to reuse the tokens for arbitrary protocols. Concerning a versatile token functionality we choose a simple signature functionality, i.e. the tokens can be instantiated with currently available signature cards. Based on this we present solutions for a large class of cryptographic tasks.

2018

PKC

Non-malleability vs. CCA-Security: The Case of Commitments
Abstract

In this work, we settle the relations among a variety of security notions related to non-malleability and CCA-security that have been proposed for commitment schemes in the literature. Interestingly, all our separations follow from two generic transformations. Given two appropriate security notions X and Y from the class of security notions we compare, these transformations take a commitment scheme that fulfills notion X and output a commitment scheme that still fulfills notion X but not notion Y.Using these transformations, we are able to show that some of the known relations for public-key encryption do not carry over to commitments. In particular, we show that, surprisingly, parallel non-malleability and parallel CCA-security are not equivalent for commitment schemes. This stands in contrast to the situation for public-key encryption where these two notions are equivalent as shown by Bellare et al. at CRYPTO ‘99.

2013

JOFC

Polynomial Runtime and Composability
Abstract

We devise a notion of polynomial runtime suitable for the simulation-based security analysis of multi-party cryptographic protocols. Somewhat surprisingly, straightforward notions of polynomial runtime lack expressivity for reactive tasks and/or lead to an unnatural simulation-based security notion. Indeed, the problem has been recognized in previous works, and several notions of polynomial runtime have already been proposed. However, our new notion, dubbed reactive polynomial time, is the first to combine the following properties: it is simple enough to support simple security/runtime analyses,it is intuitive in the sense that all intuitively feasible protocols and attacks (and only those) are considered polynomial-time,it supports secure composition of protocols in the sense of a universal composition theorem. We work in the Universal Composability (UC) protocol framework. We remark that while the UC framework already features a universal composition theorem, we develop new techniques to prove secure composition in the case of reactively polynomial-time protocols and attacks.

2009

EPRINT

Polynomial Runtime and Composability
Abstract

To prove security of a multi-party cryptographic protocol, one often reduces attacks on the protocol to attacks on a suitable computational problem. Thus, if the computational problem is hard, then the protocol is secure. But to allow for a security reduction, the protocol itself and the attack on the protocol must be efficient, i.e., polynomial-time. Of course, the obvious way to enforce an overall polynomial runtime of the protocol is to require each individual protocol machine and adversarial entity to be polynomial-time. However, as the specific case of zero-knowledge protocols demonstrates, an a priori polynomial-time bound on all entities may not be an optimal choice because the running time of some machines needs to depend on that of others. As we want to be able to model arbitrary protocol tasks, we work in the Universal Composability framework (UC). This framework additionally provides strong composability guarantees. We will point out that in the UC setting, finding a useful notion of polynomial-time for the analysis of general protocols is a highly non-trivial task.
Our goal in this work is to find a good and useful definition of polynomial-time for multi-party protocols in the UC setting that matches the intuition of what is feasible. A good definition should have the following properties:
* Flexibility: All "intuitively feasible" protocols and protocol tasks should be considered polynomial-time.
* Soundness: All "intuitively feasible" attacks (i.e., adversaries) should be considered polynomial-time.
* Completeness: Only "intuitively feasible" attacks should be considered polynomial-time. In particular, this implies that the security of protocols can be reduced to computational hardness assumptions.
* Composability: The induced security notion should support secure (universal) composition of protocols.
* Simplicity: The notion should be easy to formulate, and for all practical cases, it should be easy to decide whether a protocol or attack runs in polynomial time.
The problem of finding a good definition of polynomial time in the UC framework has been considered in a number of works, but no definition satisfying the five above criteria had been found so far. This seemingly simple problem is surprisingly elusive and it is hard to come up with a definition that does not involve many technical artifacts.
In this contribution, we give a definition of polynomial time for cryptographic protocols in the UC model, called reactively polynomial, that satisfies all five properties. Our notion is simple and easy to verify. We argue for its flexibility, completeness and soundness with practical examples that are problematic with previous approaches. We give a very general composition theorem for reactively polynomial protocols. The theorem states that arbitrarily many instances of a secure protocol can be used in any larger protocol without sacrificing security. Our proof is technically different from and substantially more involved than proofs for previous protocol composition theorems (for previous definitions of polynomial runtime). We believe that it is precisely this additional proof complexity, which appears only once and for all in the proof of the composition theorem, that makes a useful definition as simple as ours possible.

2008

EPRINT

Oblivious Transfer based on the McEliece Assumptions}
Abstract

We implement one-out-of-two bit oblivious transfer (OT) based on the
assumptions used in the McEliece cryptosystem:
the hardness of decoding random binary linear codes, and the difficulty of distinguishing
a permuted generating matrix of Goppa codes from a random matrix. To our knowledge
this is the first OT reduction to these problems only.

2008

EPRINT

A CCA2 Secure Public Key Encryption Scheme Based on the McEliece Assumptions in the Standard Model
Abstract

We show that a recently proposed construction by Rosen and Segev can be used for obtaining the first public key encryption scheme based on the McEliece assumptions which is secure against adaptive chosen ciphertext attacks in the standard model.

2008

EPRINT

A Complete Treatment of 2-party SFE in the Information-Theoretic Setting with Applications to Long-Term Security
Abstract

It is well known that general secure function evaluation (SFE) with
information-theoretical (IT) security is infeasible in the secure
channels model in presence of a corrupted majority \cite{Cle86,Kil91,
Kus92, Kil00, IKLP06, Kat06}. In particular these results extend to
and are derived from the 2-party scenario, where any corrupted party
is already a corrupted majority. On the other hand \cite{BroTap07}
have recently demonstrated that a wealth of interesting functions can
be computed securely even in presence of a corrupted majority, at
least if one is willing to sacrifice robustness, thus raising
interest in a general description of these functions.
In this work we give a complete combinatorial classification of
2-party functions, by their secure computability under active,
semi-honest, passive and quantum adversaries. Our treatment is
constructive, in the sense that, if a function is computable in a
given setting, then we exhibit a protocol.
We then proceed to apply our results to gain insight into long-term
security, where we admit computational assumptions for the duration
of a computation, but require information-theoretical security
(privacy) once the computation is concluded.

2008

EPRINT

Secure Computability of Functions in the IT setting with Dishonest Majority and Applications to Long-Term Security
Abstract

It is well known that general secure function evaluation (SFE) with information-theoretical (IT) security is infeasible in presence of a corrupted majority in the standard model. On the other hand, there are SFE protocols (Goldreich et al.~[STOC'87]) that are computationally secure (without fairness) in presence of an actively corrupted majority of the participants. Now, the issue with computational assumptions is not so much that they might be unjustified at the time of protocol execution. Rather, we are usually worried about a potential violation of the privacy of sensitive data by an attacker whose power increases over time (e.g.~due to new technical developments). Therefore, we ask which functions can be computed with long-term security, where we admit computational assumptions for the duration of a computation, but require IT security (privacy) once the computation is concluded.
Toward this end we combinatorially characterize the classes of functions that can be computed IT securely in the authenticated channels model in presence of passive, semi-honest, active, and quantum adversaries (our results for quantum adversaries and in part for active adversaries are limited to the 2-party setting). In particular we obtain results on the fair computability of functions in the IT setting along the lines of the work of Gordon et al.~[STOC'08] for the computational setting. Our treatment is constructive in the sense that if a function is computable in a given setting, then we exhibit a protocol.
We show that the class of functions computable with long-term security in a very practical setting where the adversary may be active and insecure channels and a public-key infrastructure are provided is precisely the class of functions computable with IT security in the authenticated channels model in presence of a semi-honest adversary.
Finally, from our results and the work of Kushilevitz [SIAM Journal on Discrete Mathematics '92] and Kraschewski and Müller-Quade we can derive a complete combinatorial classification of functions, by secure computability and completeness under passive, semi-honest, active, and quantum adversaries.

2007

EPRINT

Bingo Voting: Secure and coercion-free voting using a trusted random number generator
Abstract

It is debatable if current direct-recording electronic voting machines can sufficiently be trusted for a use in elections. Reports about malfunctions and possible ways of manipulation abound. Voting schemes have to fulfill seemingly contradictory requirements: On one hand the election process should be verifiable to prevent electoral fraud and on the other hand each vote should be deniable to avoid coercion and vote buying.
This work presents a new verifiable and coercion-free voting scheme Bingo Voting, which is based on a trusted random number generator. As a motivation for the new scheme two coercion/vote buying attacks on voting schemes are presented which show that it can be dangerous to let the voter contribute randomness to the voting scheme.
A proof-of-concept implementation of the scheme shows the practicality of the scheme: all costly computations can be moved to a non time critical pre-voting phase.

2006

EPRINT

On the (Im-)Possibility of Extending Coin Toss
Abstract

We consider the cryptographic two-party protocol task of extending a given coin toss. The goal is to generate n common random coins from a single use of an ideal functionality which gives m<n common random coins to the parties. In the framework of Universal Composability we show the impossibility of securely extending a coin toss for statistical and perfect security. On the other hand, for computational security the existence of a protocol for coin toss extension depends on the number m of random coins which can be obtained "for free".
For the case of stand-alone security, i.e., a simulation based security definition without an environment, we present a novel protocol for unconditionally secure coin toss extension. The new protocol works for superlogarithmic m, which is optimal as we show the impossibility of statistically secure coin toss extension for smaller m.
Combining our results with already known results, we obtain a (nearly) complete characterization under which circumstances coin toss extension is possible.

2006

EPRINT

On the Necessity of Rewinding in Secure Multiparty Computation
Abstract

We investigate whether security of multiparty computation in the information-theoretic setting implies their security under concurrent composition. We show that security in the stand-alone model proven using black-box simulators in the information-theoretic setting does not imply security under concurrent composition, not even security under 2-bounded concurrent self-composition with an inefficient simulator and fixed inputs. This in particular refutes recently made claims on the equivalence of security in the stand-alone model and concurrent composition for perfect and statistical security (STOC'06). Our result strongly relies on the question whether every rewinding simulator can be transformed into an equivalent, potentially inefficient non-rewinding (straight-line) simulator. We answer this question in the negative by giving a protocol that can be proven secure using a rewinding simulator, yet that is not secure for any non-rewinding simulator.

2006

EPRINT

Long-term Security and Universal Composability
Abstract

Algorithmic progress and future technological advances threaten
today's cryptographic protocols. This may allow adversaries to break a
protocol retrospectively by breaking the underlying complexity
assumptions long after the execution of the protocol. Long-term secure
protocols, protocols that after the end of the execution do not reveal
any information to a then possibly unlimited adversary, could meet
this threat. On the other hand, in many applications, it is necessary
that a protocol is secure not only when executed alone, but within
arbitrary contexts. The established notion of universal composability
(UC) captures this requirement.
This is the first paper to study protocols which are simultaneously
long-term secure and universally composable. We show that the usual
set-up assumptions used for UC protocols (e.g., a common reference
string) are not sufficient to achieve long-term secure and composable
protocols for commitments or zero-knowledge protocols.
We give practical alternatives (e.g., signature cards) to these usual
setup-assumptions and show that these enable the implementation of the
important primitives commitment and zero-knowledge protocols.

2005

EPRINT

On Fairness in Simulatability-based Cryptographic Systems
Abstract

Simulatability constitutes the cryptographic notion of a secure refinement and has asserted its position as one of the fundamental concepts of modern cryptography. Although simulatability carefully captures that a distributed protocol does not behave any worse than an ideal specification, it however does not capture any form of liveness guarantees, i.e., that something good eventually happens in the protocol.
We show how one can extend the notion of simulatability to comprise liveness guarantees by imposing specific fairness constraints on the adversary. As the common notion of fairness based on infinite runs and eventual message delivery is not suited for reasoning about polynomial-time, cryptographic systems, we propose a new definition of fairness that enforces the delivery of messages after a polynomial number of steps. We provide strengthened variants of this definition by granting the protocol parties explicit guarantees on the maximum delay of messages. The variants thus capture fairness with explicit timeout signals, and we further distinguish between fairness with local timeouts and fairness with global timeouts.
We compare the resulting notions of fair simulatability, and provide separating examples that help to classify the strengths of the definitions and that show that the different definitions of fairness imply different variants of simulatability.

2004

EPRINT

A Synchronous Model for Multi-Party Computation and the Incompleteness of Oblivious Transfer
Abstract

This work develops a composable notion of security in a synchronous communication network to analyze cryptographic primitives and protocols in a reliable network with guaranteed delivery. In such a synchronous model the abort of protocols must be handled explicitly. It is shown that a version of *global bit commitment* which allows to identify parties that did not give proper input cannot be securely realized with the primitives *oblivious transfer* and *broadcast*. This proves that the primitives oblivious transfer and broadcast are not complete in our synchronous model of security.
In the synchronous model presented ideal functionalities as well as parties can be equipped with a ``shell'' which can delay communication until the adversary allows delivery or the number of rounds since the shell received the message exceeds a specified threshold. This additionally allows asynchronous specification of ideal functionalities and allows to model a network where messages are not necessarily delivered in the right order. If these latency times are chosen to be infinite the network is no more reliable and becomes completely asynchronous. It is shown that secure protocols in the setting of [Canetti01] or [CLOS02] can be transformed to secure realizations in the new model if latency times are chosen to be infinite.

2004

EPRINT

On the Security and Composability of the One Time Pad
Abstract

Recent experimental results in quantum cryptography have renewed the interest in information-theoretically secure ciphers. In April 2004, in Vienna a bank transfer was secured by means of a one time pad encryption, with the key material being derived from a quantum key exchange. However, in this experiment the integrity of the transmitted message remained unprotected. This can have severe consequences, if the bank transfer form itself contains no authentication mechanism and there is a known position where the amount of money or the recipient is specified. Through flipping bits at the corresponding positions in the ciphertext, the amount of transfered money or the recipient of the money can be changed.
This concrete example illustrates the necessity for a thorough theoretical analysis of information-theoretically secure cryptographic techniques that are to be deployed in practice. In this work we show how to implement a statistically secure and composable system for message passing, that is, a channel with negligible failure rate secure against unbounded adversaries, using a one time pad based cryptosystem. We prove the security of our system in an asynchronous adversarially-controlled network using the framework put forward by Backes, Pfitzmann, and Waidner. The composition theorem offered by this framework enables the use of our scheme as a building block of more complex protocols as needed in practical applications.

2003

EPRINT

On Modeling IND-CCA Security in Cryptographic Protocols
Abstract

Two common notions of security for public key encryption schemes are shown to be equivalent: we prove that indistinguishability against chosen-ciphertext attacks (IND-CCA) is in fact polynomially equivalent to (yet "slightly" weaker than) securely realizing the ideal functionality F_PKE in the general modeling of cryptographic protocols of [http://eprint.iacr.org/2000/067]. This disproves in particular the claim that security in the sense of IND-CCA strictly implies security in the sense of realizing F_PKE (see [http://eprint.iacr.org/2000/067]). Moreover, we give concrete reductions among such security notions and show that these relations hold for both uniform and non-uniform adversarial entities.

2003

EPRINT

Initiator-Resilient Universally Composable Key Exchange
Abstract

Key exchange protocols in the setting of universal composability are investigated. First we show that the ideal functionality F_KE of [CK02] cannot be realized in the presence of adaptive adversaries, thereby disproving a claim in [CK02]. We proceed to propose a modification F_KE^(i,j), which is proven to be realizable by two natural protocols for key exchange. Furthermore, sufficient conditions for securely realizing this modified functionality are given. Two notions of key exchange are introduced that allow for security statements even when one party is corrupted. Two natural key exchange protocols are proven to fulfill the "weaker" of these notions, and a construction for deriving protocols that satisfy the "stronger" notion is given.

#### Program Committees

- TCC 2019
- Crypto 2014

#### Coauthors

- Dirk Achenbach (1)
- Michael Backes (3)
- Wasilij Beskorovajnov (1)
- Jens-Matthias Bohli (1)
- Brandon Broadnax (3)
- Felix Dörre (1)
- Nico Döttling (7)
- Rafael Dowsley (3)
- Valerie Fetzer (1)
- Jeroen van de Graaf (1)
- Gunnar Hartung (2)
- Dennis Hofheinz (9)
- Alexander Koch (1)
- Daniel Kraschewski (4)
- Robin Künzler (2)
- Jeremias Mechler (2)
- Thilo Mie (1)
- Matthias Nagel (1)
- Anderson C. A. Nascimento (3)
- Tobias Nilges (5)
- Dominik Raub (4)
- Jochen Rill (1)
- Stefan Roehrich (1)
- Andy Rupp (1)
- Rainer Steinwandt (3)
- Thorsten Strufe (1)
- Dominique Unruh (11)