International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Moti Yung

Publications

Year
Venue
Title
2022
EUROCRYPT
One-Shot Fiat-Shamir-based NIZK Arguments of Composite Residuosity and Logarithmic-Size Ring Signatures in the Standard Model 📺
The standard model security of the Fiat-Shamir transform has been an active research area for many years. In breakthrough results, Canetti {\it et al.} (STOC'19) and Peikert-Shiehian (Crypto'19) showed that, under the Learning-With-Errors (LWE) assumption, it provides soundness by applying correlation-intractable (CI) hash functions to so-called {\it trapdoor} $\Sigma$-protocols. In order to be compatible with CI hash functions based on standard LWE assumptions with polynomial approximation factors, all known such protocols have been obtained via parallel repetitions of a basic protocol with binary challenges. In this paper, we consider languages related to Paillier's composite residuosity assumption (DCR) for which we give the first trapdoor $\Sigma$-protocols providing soundness in one shot, via exponentially large challenge spaces. This improvement is analogous to the one enabled by Schnorr over the original Fiat-Shamir protocol in the random oracle model. Using the correlation-intractable hash function paradigm, we then obtain simulation-sound NIZK arguments showing that an element of $\mathbb{Z}_{N^2}^\ast$ is a composite residue, which opens the door to space-efficient applications in the standard model. As a concrete example, we build logarithmic-size ring signatures (assuming a common reference string) with the shortest signature length among schemes based on standard assumptions in the standard model. We prove security under the DCR and LWE assumptions, while keeping the signature size comparable with that of random-oracle-based schemes.
2022
EUROCRYPT
Anamorphic Encryption: Private Communication against a Dictator 📺
Cryptosystems have been developed over the years under the typical prevalent setting which assumes that the receiver’s key is kept secure from the adversary, and that the choice of the message to be sent is freely performed by the sender and is kept secure from the adversary as well. Under these fundamental and basic operational assumptions, modern Cryptography has flourished over the last half a century or so, with amazing achievements: New systems (including public-key Cryptography), beautiful and useful models (including security definitions such as semantic security), and new primitives (such as zero-knowledge proofs) have been developed. Furthermore, these fundamental achievements have been translated into actual working systems, and span many of the daily human activities over the Internet. However, in recent years, there is an overgrowing pressure from many governments to allow the government itself access to keys and messages of encryption systems (under various names: escrow encryption, emergency access, communication decency acts, etc.). Numerous non-direct arguments against such policies have been raised, such as “the bad guys can utilize other encryption system” so all other cryptosystems have to be declared illegal, or that “allowing the government access is an ill-advised policy since it creates a natural weak systems security point, which may attract others (to masquerade as the government).” It remains a fundamental open issue to show directly that the above mentioned efforts by a government (called here “a dictator” for brevity) which mandate breaking of the basic operational assumption (and disallowing other cryptosystems), is, in fact, a futile exercise. This is a direct technical point which needs to be made and has not been made to date. In this work, as a technical demonstration of the futility of the dictator’s demands, we invent the notion of “Anamorphic Encryption” which shows that even if the dictator gets the keys and the messages used in the system (before anything is sent) and no other system is allowed, there is a covert way within the context of well established public-key cryptosystems for an entity to send secure messages which are, in spite of the stringent dictator conditions, hidden from the dictator itself! We feel that this may be an important direct technical argument against the nature of governments attempts to police the use of strong cryptographic systems, and we hope to stimulate further works in this direction.
2021
EUROCRYPT
"Bifurcated Cryptography" Folding Competing Cryptosystems into a Single Scheme: On Accountability vs. Anonymity in Private Signatures 📺
Over the development of modern cryptography, often, alternative cryptographic schemes are developed to achieve goals that in some important respect are orthogonal. Thus, we have to choose either a scheme which achieves the first goal and not the second, or vice versa. This results in two types of schemes that compete with each other. In the basic area of user privacy, specifically in anonymous (multi-use credentials) signing, such an orthogonality exists between anonymity and accountability. The conceptual contribution of this work is to reverse the above orthogonality by design, which essentially typifies the last 25 years or so, and to suggest an alternative methodology where the opposed properties are carefully folded into a single scheme. The schemes will support both opposing properties simultaneously in a bifurcated fashion, where: - First, based on rich semantics expressed over the message's context and content, the user, etc., the relevant property is applied point-wise per message operation depending on a predicate; and - Secondly, at the same time, the schemes provide what we call ``branch-hiding;'' namely, the resulting calculated value hides from outsiders which property has actually been locally applied. Specifically, we precisely define and give the first construction and security proof of a ``Bifurcated Anonymous Signature'' (BiAS): A scheme which supports either absolute anonymity or anonymity with accountability, based on a specific contextual predicate, while being branch-hiding. This novel signing scheme has numerous applications not easily implementable or not considered before, especially because: (i) the conditional traceability does 'not' rely on a trusted authority as it is (non-interactively) encapsulated into signatures; and (ii) signers 'know' the predicate value and can make a conscious choice at each signing time. Technically, we realize BiAS from homomorphic commitments for a general family of predicates that can be represented by bounded-depth circuits. Our construction is generic and can be instantiated in the standard model from lattices and, more efficiently, from bilinear maps. In particular, the signature length is independent of the circuit size when we use commitments with suitable efficiency properties.
2021
PKC
Non-Interactive CCA2-Secure Threshold Cryptosystems: Achieving Adaptive Security in the Standard Model Without Pairings 📺
We consider threshold public-key encryption, where the decryption servers distributively hold the private key shares, and we need a threshold of these servers to decrypt the message (while the system remains secure when less than the threshold is corrupt). We investigate the notion of chosen-ciphertext secure threshold systems which has been historically hard to achieve. We further require the systems to be, both, adaptively secure (i.e., secure against a strong adversary making corruption decisions dynamically during the protocol), and non-interactive (i.e., where decryption servers do not interact amongst themselves but rather efficiently contribute, each, a single message). To date, only pairing-based implementations were known to achieve security in the standard security model without relaxation (i.e., without assuming the random oracle idealization) under the above stringent requirements. Here, we investigate how to achieve the above using other assumptions (in order to understand what other algebraic building blocks and mathematical assumptions are needed to extend the domain of encryption methods achieving the above). Specifically, we show realizations under the Decision Composite Residuosity (DCR) and Learning-With-Errors (LWE) assumptions.
2021
CRYPTO
Receiver-Anonymity in Reradomizable RCCA-Secure Cryptosystems Resolved 📺
In this work, we resolve the open problem raised by Prabhakaran and Rosulek at CRYPTO 2007, and present the first anonymous, rerandomizable, Replayable-CCA (RCCA) secure public key encryption scheme. This solution opens the door to numerous privacy-oriented applications with a highly desired RCCA security level. At the core of our construction is a non-trivial extension of smooth projective hash functions (Cramer and Shoup, EUROCRYPT 2002), and a modular generic framework developed for constructing Rand-RCCA-secure encryption schemes with receiver-anonymity. The framework gives an enhanced abstraction of the original Prabhakaran and Rosulek’s scheme (which was the first construction of Rand-RCCA-secure encryption in the standard model), where the most crucial enhancement is the first realization of the desirable property of receiver-anonymity, essential to privacy settings. It also serves as a conceptually more intuitive and generic understanding of RCCA security, which leads, for example, to new implementations of the notion. Finally, note that (since CCA security is not applicable to the privacy applications motivating our work) the concrete results and the conceptual advancement presented here, seem to substantially expand the power and relevance of the notion of Rand-RCCA-secure encryption.
2021
ASIACRYPT
Identity-Based Encryption for Fair Anonymity Applications: Defining, Implementing, and Applying Rerandomizable RCCA-secure IBE 📺
Our context is anonymous encryption schemes hiding their receiver, but in a setting which allows authorities to reveal the receiver when needed. While anonymous Identity-Based Encryption (IBE) is a natural candidate for such fair anonymity (it gives trusted authority access by design), the {\it de facto} security standard (a.k.a. IND-ID-CCA) is incompatible with the ciphertext rerandomizability which is crucial to anonymous communication. Thus, we seek to extend IND-ID-CCA security for IBE to a notion that can be meaningfully relaxed for rerandomizability while it still protects against active adversaries. To the end, inspired by the notion of replayable adaptive chosen-ciphertext attack (RCCA) security (Canetti {\it et al.}, Crypto'03), we formalize a new security notion called Anonymous Identity-Based RCCA (ANON-ID-RCCA) security for rerandomizable IBE and propose the first construction with rigorous security analysis. The core of our scheme is a novel extension of the double-strand paradigm, which was originally proposed by Golle {\it et al.} (CT-RSA'04) and later extended by Prabhakaran and Rosulek (Crypto'07), to the well-known Gentry-IBE (Eurocrypt'06). Notably, our scheme is the first IBE that simultaneously satisfies adaptive security, rerandomizability, and recipient-anonymity to date. As the application of our new notion, we design a new universal mixnet in the identity-based setting that does not require public key distribution (with fair anonymity). More generally, our new notion is also applicable to most existing rerandomizable RCCA-secure applications to eliminate the need for public key distribution infrastructure while allowing fairness.
2020
CRYPTO
Two-Sided Malicious Security for Private Intersection-Sum with Cardinality 📺
Private intersection-sum with cardinality allows two parties, where each party holds a private set and one of the parties additionally holds a private integer value associated with each element in her set, to jointly compute the cardinality of the intersection of the two sets as well as the sum of the associated integer values for all the elements in the intersection, and nothing beyond that. We present a new construction for private intersection sum with cardinality that provides malicious security with abort and guarantees that both parties receive the output upon successful completion of the protocol. A central building block for our constructions is a primitive called shuffled distributed oblivious PRF (DOPRF), which is a PRF that offers oblivious evaluation using a secret key shared between two parties, and in addition to this allows obliviously permuting the PRF outputs of several parallel oblivious evaluations. We present the first construction for shuffled DOPRF with malicious security. We further present several new sigma proof protocols for relations across Pedersen commitments, ElGamal encryptions, and Camenisch-Shoup encryptions that we use in our main construction, for which we develop new batching techniques to reduce communication. We implement and evaluate the efficiency of our protocol and show that we can achieve communication cost that is only 4-5x greater than the most efficient semi-honest protocol. When measuring monetary cost of executing the protocol in the cloud, our protocol is 25x more expensive than the semi-honest protocol. Our construction also allows for different parameter regimes that enable trade-offs between communication and computation.
2020
ASIACRYPT
Subvert KEM to Break DEM: Practical Algorithm-Substitution Attacks on Public-Key Encryption 📺
Motivated by the widespread concern about mass surveillance of encrypted communications, Bellare \textit{et al.} introduced at CRYPTO 2014 the notion of Algorithm-Substitution Attack (ASA) where the legitimate encryption algorithm is replaced by a subverted one that aims to undetectably exfiltrate the secret key via ciphertexts. Practically implementable ASAs on various cryptographic primitives (Bellare \textit{et al.}, CRYPTO'14 \& CCS'15; Ateniese \textit{et al.}, CCS'15; Berndt and Li\'{s}kiewicz, CCS'17) have been constructed and analyzed, leaking the secret key successfully. Nevertheless, in spite of much current attention, the practical impact of ASAs (formulated originally for symmetric key cryptography) on public-key (PKE) encryption operations remains unclear, primarily since the encryption operation of PKE does not involve the secret key and previously known ASAs become relatively inefficient for leaking the plaintext due to the logarithmic upper bound of exfiltration rate (Berndt and Li\'{s}kiewicz, CCS'17). In this work, we formulate a practical ASA on PKE encryption algorithm which, perhaps surprisingly, turns out to be much more efficient and robust than existing ones, showing that ASAs on PKE schemes are far more dangerous than previously believed. We mainly target PKE of hybrid encryption which is the most prevalent way to employ PKE in the literature and in practical systems. The main strategy of our ASA is to subvert the underlying key encapsulation mechanism (KEM) so that the session key encapsulated could be efficiently extracted, which, in turn, breaks the data encapsulation mechanism (DEM) enabling us to learn the plaintext itself. Concretely, our non-black-box attack enables recovering the plaintext from only two successive ciphertexts and minimally depends on a short state of previous internal randomness. A widely used class of KEMs is shown to be subvertible by our powerful attack. Our attack relies on a novel identification and formalization of specific non-black-box yet general enough properties that yield practical ASAs on KEMs. More broadly, this may shed some light on exploring the structural weakness of other composed cryptographic primitives, which may make them susceptible to more dangerous ASAs that surpass the logarithmic upper bound of exfiltration rate on universal ASAs.
2020
JOFC
Adaptively Secure Non-interactive CCA-Secure Threshold Cryptosystems: Generic Framework and Constructions
Benoît Libert Moti Yung
In threshold cryptography, private keys are divided into n shares, each one of which is given to a different server in order to avoid single points of failure. In the case of threshold public-key encryption, at least $$t \le n$$ t ≤ n servers need to contribute to the decryption process. A threshold primitive is said robust if no coalition of t malicious servers can prevent remaining honest servers from successfully completing private key operations. Non-interactive schemes, considered the most practical ones, allow servers to contribute to decryption without interactions. So far, most non-interactive threshold cryptosystems were only proved secure against static corruptions. In the adaptive corruption scenario (where the adversary can corrupt servers at any time, based on its complete view), all existing robust threshold encryption schemes that also resist chosen-ciphertext attacks till recently require interaction in the decryption phase. A very specific method (in composite order groups) for getting rid of interaction was recently suggested, leaving the question of more generic frameworks and constructions with better security and, in particular, better flexibility (i.e., compatibility with distributed key generation). This paper advances the state of the art and describes a general construction of adaptively secure robust non-interactive threshold cryptosystems with chosen-ciphertext security. We define the novel notion of all-but-one perfectly sound threshold hash proof systems that can be seen as (threshold) hash proof systems with publicly verifiable and simulation-sound proofs. We show that this notion generically implies threshold cryptosystems combining the aforementioned properties. Then, we provide efficient instantiations under well-studied assumptions in bilinear groups (e.g., in such groups of prime order). These instantiations have a tighter security proof in the single-challenge setting and are indeed compatible with distributed key generation protocols.
2019
PKC
Let a Non-barking Watchdog Bite: Cliptographic Signatures with an Offline Watchdog
We study how to construct secure digital signature schemes in the presence of kleptographic attacks. Our work utilizes an offline watchdog to clip the power of subversions via only one-time black-box testing of the implementation. Previous results essentially rely on an online watchdog which requires the collection of all communicating transcripts (or active re-randomization of messages).We first give a simple but generic construction, without random oracles, in the partial-subversion model in which key generation and signing algorithms can be subverted. Then, we give the first digital signature scheme in the complete-subversion model in which all cryptographic algorithms can be subverted. This construction is based on the full-domain hash. Along the way, we enhance the recent result of Russell et al.  (CRYPTO 2018) about correcting a subverted random oracle.
2018
CRYPTO
Correcting Subverted Random Oracles 📺
The random oracle methodology has proven to be a powerful tool for designing and reasoning about cryptographic schemes, and can often act as an effective bridge between theory and practice. In this paper, we focus on the basic problem of correcting faulty—or adversarially corrupted—random oracles, so that they can be confidently applied for such cryptographic purposes.We prove that a simple construction can transform a “subverted” random oracle—which disagrees with the original one at a negligible fraction of inputs—into a construction that is indifferentiable from a random function. Our results permit future designers of cryptographic primitives in typical kleptographic settings (i.e., with adversaries who may subvert the implementation of cryptographic algorithms but undetectable via blackbox testing) to use random oracles as a trusted black box, in spite of not trusting the implementation. Our analysis relies on a general rejection re-sampling lemma which is a tool of possible independent interest.
2016
ASIACRYPT
2016
JOFC
2015
TCC
2015
PKC
2015
CRYPTO
2015
ASIACRYPT
2015
CHES
2014
EUROCRYPT
2014
PKC
2014
ASIACRYPT
2014
ASIACRYPT
2013
PKC
2013
CRYPTO
2013
ASIACRYPT
2012
TCC
2012
EUROCRYPT
2012
CRYPTO
2012
PKC
2011
TCC
2011
FSE
2011
EUROCRYPT
2011
ASIACRYPT
2010
TCC
2010
EUROCRYPT
2009
ASIACRYPT
2009
ASIACRYPT
2009
EUROCRYPT
2009
EUROCRYPT
2009
EUROCRYPT
2008
PKC
2007
ASIACRYPT
2007
ASIACRYPT
2007
EUROCRYPT
2007
PKC
2007
JOFC
2006
ASIACRYPT
2006
TCC
2006
TCC
2006
JOFC
2006
PKC
2005
EUROCRYPT
2004
ASIACRYPT
2004
EUROCRYPT
2004
EUROCRYPT
2004
PKC
2004
PKC
2003
CRYPTO
2003
EUROCRYPT
2003
PKC
2002
ASIACRYPT
2002
ASIACRYPT
Crypto-integrity
Moti Yung
2002
EUROCRYPT
2002
EUROCRYPT
2002
PKC
2001
CHES
2001
CRYPTO
2001
EUROCRYPT
2001
FSE
2001
PKC
2001
PKC
2000
ASIACRYPT
2000
FSE
2000
PKC
2000
PKC
2000
PKC
1999
ASIACRYPT
1999
FSE
1999
PKC
1999
PKC
1998
ASIACRYPT
1998
EUROCRYPT
1998
FSE
1998
PKC
1998
PKC
1998
PKC
1998
JOFC
1997
CRYPTO
1997
CRYPTO
1997
CRYPTO
1997
EUROCRYPT
1997
EUROCRYPT
1997
EUROCRYPT
1997
FSE
1996
ASIACRYPT
1996
CRYPTO
1996
CRYPTO
1996
EUROCRYPT
1996
JOFC
1995
CRYPTO
1995
CRYPTO
1995
CRYPTO
1994
EUROCRYPT
1993
EUROCRYPT
1992
CRYPTO
1992
CRYPTO
1992
CRYPTO
1991
CRYPTO
1991
EUROCRYPT
1990
CRYPTO
1990
CRYPTO
1990
CRYPTO
1990
EUROCRYPT
1989
EUROCRYPT
1989
EUROCRYPT
1989
EUROCRYPT
1987
CRYPTO
1987
CRYPTO
1985
CRYPTO
1984
CRYPTO

Program Committees

Eurocrypt 2018
PKC 2016
TCC 2012
Crypto 2009
PKC 2008
Eurocrypt 2008
PKC 2007
FSE 2006
PKC 2006
Asiacrypt 2006
FSE 2005
PKC 2005
Eurocrypt 2005
Asiacrypt 2004
PKC 2004
Asiacrypt 2003
PKC 2003
Crypto 2002 (Program chair)
PKC 2002
Asiacrypt 2001
PKC 2001
PKC 2000
Eurocrypt 2000
Asiacrypt 2000
Crypto 1999
Eurocrypt 1998
Crypto 1998
Asiacrypt 1996
Eurocrypt 1995
Eurocrypt 1994
Crypto 1994
Crypto 1991

Coauthors

Aydin Aysu (1)
Mihir Bellare (3)
Ray Bird (1)
Carlo Blundo (1)
Gilles Brassard (2)
Ernest F. Brickell (1)
Enrico Buonanno (1)
Jan Camenisch (1)
Julien Cathalo (1)
Donghoon Chang (2)
Rongmao Chen (3)
Seung Geol Choi (3)
Sherman S. M. Chow (1)
Ronald Cramer (1)
Claude Crépeau (1)
Giovanni Di Crescenzo (1)
Yi Deng (1)
Yvo Desmedt (2)
Julien Devevey (1)
Yevgeniy Dodis (4)
Ariel Elbaz (2)
Dengguo Feng (1)
Yair Frankel (9)
Matthew K. Franklin (2)
Zvi Galil (3)
Juan A. Garay (1)
Ran Gelles (1)
Peter Gemmell (1)
Inder S. Gopal (1)
Vipul Goyal (1)
Ege Gulcan (1)
Stuart Haber (3)
Helena Handschuh (1)
Amir Herzberg (3)
Xinyi Huang (3)
Russell Impagliazzo (1)
Markus Jakobsson (4)
Philippe A. Janson (1)
Stanislaw Jarecki (1)
David S. Johnson (1)
Marc Joye (6)
Ari Juels (1)
Ali Juma (1)
Jonathan Katz (9)
Aggelos Kiayias (11)
Eike Kiltz (1)
Hugo Krawczyk (1)
Shay Kutten (2)
Dong Hoon Lee (2)
Sangjin Lee (1)
Kwangsu Lee (2)
Benoît Libert (17)
Dongdai Lin (1)
Philip D. MacKenzie (4)
Tal Malkin (8)
Luke McAven (1)
Peihan Miao (1)
Petros Mol (1)
Refik Molva (1)
Daisuke Moriyama (1)
Mridul Nandi (2)
Moni Naor (2)
Khoa Nguyen (3)
Jianting Ning (1)
Satoshi Obana (1)
Tatsuaki Okamoto (2)
Rafail Ostrovsky (4)
Jong Hwan Park (1)
Sarvar Patel (1)
Giuseppe Persiano (1)
Thomas Peters (12)
Duong Hieu Phan (1)
Krzysztof Pietrzak (1)
David Pointcheval (1)
Jean-Jacques Quisquater (1)
Mariana Raykova (1)
Alexander Russell (3)
Reihaneh Safavi-Naini (1)
Amit Sahai (1)
Alfredo De Santis (3)
Patrick Schaumont (1)
Berry Schoenmakers (1)
Karn Seth (1)
Martijn Stam (1)
François-Xavier Standaert (1)
Julien P. Stern (1)
Qiang Tang (3)
Isamu Teranishi (3)
Yiannis Tsiounis (6)
Ugo Vaccaro (1)
Yevgeniy Vahlis (2)
Serge Vaudenay (1)
Ramarathnam Venkatesan (3)
Bin Wang (2)
Ying Wang (2)
Shouhuai Xu (2)
Aleksandr Yampolskiy (1)
Guomin Yang (1)
Andrew Chi-Chih Yao (1)
Adam Young (11)
Yunlei Zhao (3)
Yongjun Zhao (1)
Hong-Sheng Zhou (3)