International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Jörn Müller-Quade

Publications

Year
Venue
Title
2024
PKC
Chosen-Ciphertext Secure Dual-Receiver Encryption in the Standard Model Based on Post-Quantum Assumptions
Dual-receiver encryption (DRE) is a special form of public key encryption (PKE) that allows a sender to encrypt a message for two recipients. Without further properties, the difference between DRE and PKE is only syntactical. One such important property is soundness, which requires that no ciphertext can be constructed such that the recipients decrypt to different plaintexts. Many applications rely on this property in order to realize more complex protocols or primitives. In addition many of these applications explicitly avoid the usage of the random oracle, which poses an additional requirement on a DRE construction. We show that all of the IND-CCA2 secure standard model DRE constructions based on post-quantum assumptions fall short of augmenting the constructions with soundness and describe attacks thereon. We then give an overview over all applications of IND-CCA2 secure DRE, group them into generic (i. e., applications using DRE as black-box) and non-generic applications and demonstrate that all generic ones require either soundness or public verifiability. Conclusively, we identify the gap of IND-CCA2 secure DRE constructions with soundness based on post-quantum assumptions in the standard model. In order to fill this gap we provide two direct IND-CCA2 secure DRE constructions based on the standard post-quantum assumptions, Normal Form Learning With Errors (NLWE) and Learning Paritiy with Noise (LPN).
2023
PKC
Sender-binding Key Encapsulation
Secure communication is gained by combining encryption with authentication. In real-world applications encryption commonly takes the form of KEM-DEM hybrid encryption, which is combined with ideal authentication. The pivotal question is how weak the employed key encapsulation mechanism (KEM) is allowed to be to still yield universally composable (UC) secure communication when paired with symmetric encryption and ideal authentication. This question has so far been addressed for public-key encryption (PKE) only, showing that encryption does not need to be stronger than sender-binding CPA, which binds the CPA secure ciphertext non-malleably to the sender ID. For hybrid encryption, prior research unanimously reaches for CCA2 secure encryption which is unnecessarily strong. Answering this research question is vital to develop more efficient and feasible protocols for real-world secure communication and thus enable more communication to be conducted securely. We use ideas from the PKE setting to develop new answers for hybrid encryption in this paper. This allows us to develop a new and significantly weaker security notion—sender-binding CPA for KEMs—which is still strong enough for secure communication. By using game-based notions as building blocks, we attain secure communication in the form of ideal functionalities with proofs in the UC-framework. Secure communication is reached in both the classic as well as session context by adding authentication and one-time and replayable CCA secure symmetric encryption respectively. We furthermore provide an efficient post-quantum secure LWE-based construction in the standard model giving a first indication of the real-world benefit resulting from our new security notion. Overall we manage to make significant progress on discovering the minimal security requirements for hybrid encryption components to facilitate secure communication.
2023
ASIACRYPT
Universally Composable Auditable Surveillance
User privacy is becoming increasingly important in our digital society. Yet, many applications face legal requirements or regulations that prohibit unconditional anonymity guarantees, e.g., in electronic payments where surveillance is mandated to investigate suspected crimes. As a result, many systems have no effective privacy protections at all, or have backdoors, e.g., stored at the operator side of the system, that can be used by authorities to disclose a user’s private information (e.g., lawful interception). The problem with such backdoors is that they also enable silent mass surveillance within the system. To prevent such misuse, various approaches have been suggested which limit possible abuse or ensure it can be detected. Many works consider auditability of surveillance actions but do not enforce that traces are left when backdoors are retrieved. A notable exception which offers retrospective and silent surveillance is the recent work on misuse-resistant surveillance by Green et al. (EUROCRYPT’21). However, their approach relies on extractable witness encryption, which is a very strong primitive with no known efficient and secure implementations. In this work, we develop a building block for auditable surveillance. In our protocol, backdoors or escrow secrets of users are protected in multiple ways: (1) Backdoors are short-term and user-specific; (2) they are shared between trustworthy parties to avoid a single point of failure; and (3) backdoor access is given conditionally. Moreover (4) there are audit trails and public statistics for every (granted) backdoor request; and (5) surveillance remains silent, i.e., users do not know they are surveilled. Concretely, we present an abstract UC-functionality which can be used to augment applications with auditable surveillance capabilities. Our realization makes use of threshold encryption to protect user secrets, and is concretely built in a blockchain context with committee-based YOSO MPC. As a consequence, the committee can verify that the conditions for backdoor access are given, e.g., that law enforcement is in possession of a valid surveillance warrant (via a zero-knowledge proof). Moreover, access leaves an audit trail on the ledger, which allows an auditor to retrospectively examine surveillance decisions. As a toy example, we present an Auditably Sender-Traceable Encryption scheme, a PKE scheme where the sender can be deanonymized by law enforcement. We observe and solve problems posed by retrospective surveillance via a special non-interactive non-committing encryption scheme which allows zero-knowledge proofs over message, sender identity and (escrow) secrets.
2023
ASIACRYPT
Practically Efficient Private Set Intersection From Trusted Hardware with Side-Channels
Felix Dörre Jeremias Mechler Jörn Müller-Quade
Private set intersection (PSI) is one of the most important privacy-enhancing technologies with applications such as malware and spam detection, recognition of child pornography, contact discovery, or, more recently, contact tracing. In this paper, we investigate how PSI can be constructed and implemented simply and practically efficient. To this end, a natural possibility is the use of trusted execution environments (TEEs), which are commonly used in place of a trusted third party due to their presumed security guarantees. However, this trust is often not warranted: Today’s TEEs like Intel SGX suffer from a number of side-channels that allow the host to learn secrets of a TEE, unless countermeasures are taken. Furthermore, due to the high complexity and closed-source nature, it cannot be ruled out that a TEE is passively corrupted, i.e. leaks secrets to the manufacturer or a government agency such as the NSA. When constructing a protocol using TEEs, such (potential) vulnerabilities need to be accounted for. Otherwise, all security may be lost. We propose a protocol for two-party PSI whose security holds in a setting where TEEs cannot be fully trusted, e.g. due to the existence of side-channels. In particular, we deal with the possibilities that i) the TEE is completely transparent for the host, except for very simple secure cryptographic operations or ii) that it leaks all secrets to a third party, e.g. the manufacturer. Even in this challenging setting, our protocol is not only very fast, but also conceptually simple, which is an important feature as more complex protocols tend to be implemented with subtle security faults. To formally capture this setting, we define variants of the ideal functionality for TEEs due to Pass et al. (EUROCRYPT 2017). Using these functionalities, we prove our protocol’s security, which holds under universal composition. To illustrate the usefulness of our model, we sketch other possible applications like (randomized) oblivious transfer or private computation of the Hamming distance. Our PSI implementation, which uses Intel SGX as TEE, computes the intersection between two sets with 2^24 128-bit elements in 7.3 seconds. This makes our protocol the fastest PSI protocol to date with respect to single-threaded performance.
2023
TCC
Composable Long-Term Security with Rewinding
Long-term security, a variant of Universally Composable (UC) security introduced by Müller-Quade and Unruh (TCC ’07, JoC ’10), allows to analyze the security of protocols in a setting where all hardness assumptions no longer hold after the protocol execution has finished. Such a strict notion is highly desirable when properties such as input privacy need to be guaranteed for a long time, e.g. with zero-knowledge proofs for secure electronic voting. Strong impossibility results rule out so-called long-term-revealing setups, e.g. a common reference string (CRS), to achieve long-term security, with known constructions for long-term security requiring hardware assumptions, e.g. signature cards. We circumvent these impossibility results with new techniques, enabling rewinding-based simulation in a way that universal composability is achieved. This allows us to construct a long-term-secure composable commitment scheme in the CRS-hybrid model, which is provably impossible in the notion of Müller-Quade and Unruh. We base our construction on a statistically hiding commitment scheme in the CRS-hybrid model with CCA-like properties. To provide a CCA oracle, we cannot rely on super-polynomial extraction techniques and instead extract the value committed to via rewinding. To this end, we incorporate rewinding-based commitment extraction into the UC framework via a helper in analogy to Canetti, Lin and Pass (FOCS 2010), allowing both adversary and environment to extract statistically hiding commitments. Our new framework provides the first setting in which a commitment scheme that is both statistically hiding and universally composable can be constructed from standard polynomial-time hardness assumptions and a CRS only. We also prove that our CCA oracle is k-robust extractable. This asserts that extraction is possible without rewinding a concurrently executed k-round protocol. Consequently any k-round (standard) UC-secure protocol remains secure in the presence of our helper. Finally, we prove that building long-term-secure oblivious transfer (and thus general two-party computations) from long-term-revealing setups remains impossible in our setting. Still, our long-term-secure commitment scheme suffices for natural applications, such as long-term secure and composable (commit-and-prove) zero-knowledge arguments of knowledge.
2022
PKC
A New Security Notion for PKC in the Standard Model: Weaker, Simpler, and Still Realizing Secure Channels 📺
Encryption satisfying CCA2 security is commonly known to be unnecessarily strong for realizing secure channels. Moreover, CCA2 constructions in the standard model are far from being competitive practical alternatives to constructions via random oracle. A promising research area to alleviate this problem are weaker security notions—like IND-RCCA secure encryption or IND-atag-wCCA secure tag-based encryption—which are still able to facilitate secure message transfer (SMT) via authenticated channels. In this paper we introduce the concept of sender-binding encryption (SBE), unifying prior approaches of SMT construction in the universal composability (UC) model. We furthermore develop the corresponding non-trivial security notion of IND-SB-CPA and formally prove that it suffices for realizing SMT in conjunction with authenticated channels. Our notion is the weakest so far in the sense that it can be generically constructed from the weakest prior notions—RCCA and atag-wCCA—without additional assumptions, while the reverse is not true. A direct consequence is that IND-stag-wCCA, which is strictly weaker than IND-atag-wCCA but stronger than our IND-SB-CPA, can be used to construct a secure channel. Finally, we give an efficient IND-SB-CPA secure construction in the standard model from IND-CPA secure double receiver encryption (DRE) based on McEliece. This shows that IND-SB-CPA security yields simpler and more efficient constructions in the standard model than the weakest prior notions, i.e., IND-atag-wCCA and IND-stag-wCCA.
2021
ASIACRYPT
ConTra Corona: Contact Tracing against the Coronavirus by Bridging the Centralized–Decentralized Divide for Stronger Privacy 📺
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 📺
Brandon Broadnax Jeremias Mechler Jörn Müller-Quade
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
Jeremias Mechler Jörn Müller-Quade Tobias Nilges
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
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.
2017
EUROCRYPT
2015
TCC
2013
TCC
2013
EUROCRYPT
2013
JOFC
Polynomial Runtime and Composability
Dennis Hofheinz Dominique Unruh Jörn Müller-Quade
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.
2012
ASIACRYPT
2011
TCC
2011
TCC
2010
JOFC
2010
CRYPTO
2009
TCC
2007
TCC
2007
TCC
2006
EUROCRYPT
2004
TCC

Program Committees

TCC 2019
Crypto 2014