## CryptoDB

### Eike Kiltz

#### Publications

Year
Venue
Title
2019
EUROCRYPT
We propose a modular security treatment of blind signatures derived from linear identification schemes in the random oracle model. To this end, we present a general framework that captures several well known schemes from the literature and allows to prove their security. Our modular security reduction introduces a new security notion for identification schemes called One-More-Man In the Middle Security which we show equivalent to the classical One-More-Unforgeability notion for blind signatures.We also propose a generalized version of the Forking Lemma due to Bellare and Neven (CCS 2006) and show how it can be used to greatly improve the understandability of the classical security proofs for blind signatures schemes by Pointcheval and Stern (Journal of Cryptology 2000).
2018
JOFC
2018
EUROCRYPT
2018
CRYPTO
One of the most important and successful tools for assessing hardness assumptions in cryptography is the Generic Group Model (GGM). Over the past two decades, numerous assumptions and protocols have been analyzed within this model. While a proof in the GGM can certainly provide some measure of confidence in an assumption, its scope is rather limited since it does not capture group-specific algorithms that make use of the representation of the group.To overcome this limitation, we propose the Algebraic Group Model (AGM), a model that lies in between the Standard Model and the GGM. It is the first restricted model of computation covering group-specific algorithms yet allowing to derive simple and meaningful security statements. To prove its usefulness, we show that several important assumptions, among them the Computational Diffie-Hellman, the Strong Diffie-Hellman, and the interactive LRSW assumptions, are equivalent to the Discrete Logarithm (DLog) assumption in the AGM. On the more practical side, we prove tight security reductions for two important schemes in the AGM to DLog or a variant thereof: the BLS signature scheme and Groth’s zero-knowledge SNARK (EUROCRYPT 2016), which is the most efficient SNARK for which only a proof in the GGM was known. Our proofs are quite simple and therefore less prone to subtle errors than those in the GGM.Moreover, in combination with known lower bounds on the Discrete Logarithm assumption in the GGM, our results can be used to derive lower bounds for all the above-mentioned results in the GGM.
2018
PKC
We initiate the study of public-key encryption (PKE) schemes and key-encapsulation mechanisms (KEMs) that retain security even when public parameters (primes, curves) they use may be untrusted and subverted. We define a strong security goal that we call ciphertext pseudo-randomness under parameter subversion attack (CPR-PSA). We also define indistinguishability (of ciphertexts for PKE, and of encapsulated keys from random ones for KEMs) and public-key hiding (also called anonymity) under parameter subversion attack, and show they are implied by CPR-PSA, for both PKE and KEMs. We show that hybrid encryption continues to work in the parameter subversion setting to reduce the design of CPR-PSA PKE to CPR-PSA KEMs and an appropriate form of symmetric encryption. To obtain efficient, elliptic-curve-based KEMs achieving CPR-PSA, we introduce efficiently-embeddable group families and give several constructions from elliptic-curves.
2018
PKC
This paper contributes to understanding the interplay of security notions for PKE, KEMs, and DEMs, in settings with multiple users, challenges, and instances. We start analytically by first studying (a) the tightness aspects of the standard hybrid KEM+DEM encryption paradigm, (b) the inherent weak security properties of all deterministic DEMs due to generic key-collision attacks in the multi-instance setting, and (c) the negative effect of deterministic DEMs on the security of hybrid encryption.We then switch to the constructive side by (d) introducing the concept of an augmented data encapsulation mechanism (ADEM) that promises robustness against multi-instance attacks, (e) proposing a variant of hybrid encryption that uses an ADEM instead of a DEM to alleviate the problems of the standard KEM+DEM composition, and (f) constructing practical ADEMs that are secure in the multi-instance setting.
2018
TCHES
In this paper, we present the lattice-based signature scheme Dilithium, which is a component of the CRYSTALS (Cryptographic Suite for Algebraic Lattices) suite that was submitted to NIST’s call for post-quantum cryptographic standards. The design of the scheme avoids all uses of discrete Gaussian sampling and is easily implementable in constant-time. For the same security levels, our scheme has a public key that is 2.5X smaller than the previously most efficient lattice-based schemes that did not use Gaussians, while having essentially the same signature size. In addition to the new design, we significantly improve the running time of the main component of many lattice-based constructions – the number theoretic transform. Our AVX2-based implementation results in a speed-up of roughly a factor of 2 over the previously best algorithms that appear in the literature. The techniques for obtaining this speed-up also have applications to other lattice-based schemes.
2017
CRYPTO
2017
ASIACRYPT
2017
TCC
2017
TCC
2017
JOFC
2017
JOFC
2017
JOFC
2016
EUROCRYPT
2016
CRYPTO
2016
TCC
2016
TCC
2015
JOFC
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
TCC
2015
PKC
2015
PKC
2015
PKC
2015
EUROCRYPT
2015
CRYPTO
2014
CRYPTO
2014
PKC
2014
EPRINT
2013
PKC
2013
CRYPTO
2013
CRYPTO
2012
EUROCRYPT
2012
EUROCRYPT
2012
EUROCRYPT
2012
PKC
2012
ASIACRYPT
2012
FSE
2012
JOFC
We introduce a new lattice-based cryptographic structure called a bonsai tree, and use it to resolve some important open problems in the area. Applications of bonsai trees include an efficient, stateless ‘hash-and-sign’ signature scheme in the standard model (i.e., no random oracles), and the first hierarchical identity-based encryption (HIBE) scheme (also in the standard model) that does not rely on bilinear pairings. Interestingly, the abstract properties of bonsai trees seem to have no known realization in conventional number-theoretic cryptography.
2012
JOFC
We introduce a new combinatorial primitive called programmable hash functions (PHFs). PHFs can be used to program the output of a hash function such that it contains solved or unsolved discrete logarithm instances with a certain probability. This is a technique originally used for security proofs in the random oracle model. We give a variety of standard model realizations of PHFs (with different parameters).The programmability makes PHFs a suitable tool to obtain black-box proofs of cryptographic protocols when considering adaptive attacks. We propose generic digital signature schemes from the strong RSA problem and from some hardness assumption on bilinear maps that can be instantiated with any PHF. Our schemes offer various improvements over known constructions. In particular, for a reasonable choice of parameters, we obtain short standard model digital signatures over bilinear maps.
2011
EUROCRYPT
2011
ASIACRYPT
2010
TCC
2010
TCC
2010
EPRINT
This paper proposes practical chosen-ciphertext secure public-key encryption systems that are provably secure under the computational Diffie-Hellman assumption, in the standard model. Our schemes are conceptually simpler and more efficient than previous constructions. We also show that in bilinear groups the size of the public-key can be shrunk from n to 2\sqrt{n} group elements, where n is the security parameter.
2010
PKC
2010
PKC
2010
ASIACRYPT
2010
CRYPTO
2010
EUROCRYPT
2010
EUROCRYPT
2010
EUROCRYPT
2009
PKC
2009
JOFC
2009
EUROCRYPT
2009
EUROCRYPT
2009
EUROCRYPT
2009
CRYPTO
2008
EUROCRYPT
2008
EPRINT
We propose two constructions of chosen-ciphertext secure identity-based encryption (IBE) schemes. Our schemes have a security proof in the standard model, yet they offer performance competitive with all known random-oracle based schemes. The efficiency improvement is obtained by combining modifications of the IBE schemes by Waters and Gentry with authenticated symmetric encryption.
2008
EPRINT
We consider a hybrid version of Damgård's ElGamal public-key encryption scheme that incorporates the use of a symmetric cipher and a hash function for key-derivation. We prove that under appropriate choice of the hash function this scheme is IND-CCA secure under the Decisional Diffie-Hellman assumption in the standard model. Our results can be generalized to universal hash proof systems where our main technical contribution can be viewed as an efficient generic transformation from 1-universal to 2-universal hash proof systems.
2008
EPRINT
We present a new approach to the design of IND-CCA2 secure hybrid encryption schemes in the standard model. Our approach provides an efficient generic transformation from 1-universal to 2-universal hash proof systems. The transformation involves a randomness extractor based on a 4-wise independent hash function as the key derivation function. Our methodology can be instantiated with efficient schemes based on standard intractability assumptions such as DDH, QR and Paillier. Interestingly, our framework also allows to prove IND-CCA2 security of a hybrid version of 1991s Damgaards ElGamal public-key encryption scheme under the DDH assumption.
2008
ASIACRYPT
2008
JOFC
2008
EPRINT
We propose a new computational problem called the twin Diffie-Hellman problem. This problem is closely related to the usual (computational) Diffie-Hellman problem and can be used in many of the same cryptographic constructions that are based on the Diffie-Hellman problem. Moreover, the twin Diffie-Hellman problem is at least as hard as the ordinary Diffie-Hellman problem. However, we are able to show that the twin Diffie-Hellman problem remains hard, even in the presence of a decision oracle that recognizes solutions to the problem  this is a feature not enjoyed by the ordinary Diffie-Hellman problem. In particular, we show how to build a certain trapdoor test that allows us to effectively answer such decision oracle queries without knowing any of the corresponding discrete logarithms. Our new techniques have many applications. As one such application, we present a new variant of ElGamal encryption with very short ciphertexts, and with a very simple and tight security proof, in the random oracle model, under the assumption that the ordinary Diffie-Hellman problem is hard. We present several other applications as well, including: a new variant of Diffie and Hellmans non-interactive key exchange protocol; a new variant of Cramer-Shoup encryption, with a very simple proof in the standard model; a new variant of Boneh-Franklin identity-based encryption, with very short ciphertexts; a more robust version of a password-authenticated key exchange protocol of Abdalla and Pointcheval.
2008
CRYPTO
2007
ASIACRYPT
2007
CRYPTO
2007
CRYPTO
2007
PKC
2007
TCC
2007
EPRINT
In this note we remark that the inversion-based selective-ID secure identity-based encryption (IBE) scheme from Boneh and Boyen can be bootstrapped to full-ID security using a technique by Waters.
2007
EPRINT
This paper deals with generic transformations from ID-based key encapsulation mechanisms (IBKEM) to hybrid public-key encryption (PKE). The best generic transformation known until now is by Boneh and Katz and requires roughly 704-bit overhead in the ciphertext. We present two new such generic transformations that are applicable to partitioned IBKEMs. A partitioned IBKEM is an IBKEM that provides some extra structure. Such IBKEMs are quite natural and in fact nearly all known IBKEMs have this additional property. Our first transformation yields chosen-ciphertext secure PKE schemes from selective-ID secure partitioned IBKEMs with a 256-bit overhead in ciphertext size plus one extra exponentiation in encryption/decryption. As the central tool a Chameleon Hash function is used to map the identities. The second transformation transforms adaptive-ID secure partitioned IBKEMs into chosen-ciphertext secure PKE schemes with no additional overhead. Applying our transformations to existing IBKEMs we propose a number of novel PKE schemes with different trade-offs. In some concrete instantiations the Chameleon Hash can be made “implicit” which results in improved efficiency by eliminating the additional exponentiation. Since our transformations preserve the public verifiability property of the IBE schemes it is possible to extend our results to build threshold hybrid PKE schemes. We show an analogue generic transformation in the threshold setting and present a concrete scheme which results in the most efficient threshold PKE scheme in the standard model.
2007
EPRINT
We propose a practical key encapsulation mechanism with a simple and intuitive design concept. Security against chosen-ciphertext attacks can be proved in the standard model under a new assumption, the Gap Hashed Diffie-Hellman (GHDH) assumption. The security reduction is tight and simple. Secure key encapsulation, combined with an appropriately secure symmetric encryption scheme, yields a hybrid public-key encryption scheme which is secure against chosen-ciphertext attacks. The implied encryption scheme is very efficient: compared to the previously most efficient scheme by Kurosawa and Desmedt [Crypto 2004] it has 128 bits shorter ciphertexts, between 25-50% shorter public/secret keys, and it is slightly more efficient in terms of encryption/decryption speed. Furthermore, our scheme enjoys (the option of) public verifiability of the ciphertexts and it inherits all practical advantages of secure hybrid encryption.
2007
EPRINT
In this paper, we introduce a new primitive called identity-based encryption with wildcard key derivation (WKD-IBE, or "wicked IBE") that enhances the concept of hierarchical identity-based encryption (HIBE) by allowing more general key delegation patterns. A secret key is derived for a vector of identity strings, where entries can be left blank using a wildcard. This key can then be used to derive keys for any pattern that replaces wildcards with concrete identity strings. For example, one may want to allow the university's head system administrator to derive secret keys (and hence the ability to decrypt) for all departmental sysadmin email addresses sysadmin@*.univ.edu, where * is a wildcard that can be replaced with any string. We provide appropriate security notions and provably secure instantiations with different tradeoffs in terms of ciphertext size and efficiency. We also present a generic construction of identity-based broadcast encryption (IBBE) from any WKD-IBE scheme. One of our instantiation yields an IBBE scheme with constant ciphertext size.
2007
EPRINT
We put forward a new paradigm for building hybrid encryption schemes from constrained chosen-ciphertext secure (CCCA) key-encapsulation mechanisms (KEMs) plus authenticated symmetric encryption. Constrained chosen-ciphertext security is a new security notion for KEMs that we propose. CCCA has less demanding security requirements than standard chosen-ciphertext (CCA) security (since it requires the adversary to have a certain plaintext-knowledge when making a decapsulation query) yet we can prove that CCCA is sufficient for secure hybrid encryption. Our notion is not only useful to express the Kurosawa-Desmedt public-key encryption scheme and its generalizations to hash-proof systems in an abstract KEM/DEM security framework. It also has a very constructive appeal, which we demonstrate with a new encryption scheme whose security relies on a class of intractability assumptions that we show (in the generic group model) strictly weaker than the Decision Diffie-Hellman (DDH) assumption. This appears to be the first practical public-key encryption scheme in the literature from an algebraic assumption strictly weaker than DDH.
2006
ASIACRYPT
2006
PKC
2006
TCC
2006
TCC
2006
EPRINT
We describe a new and practical identity-based key encapsulation mechanism that is secure in the standard model against chosen-ciphertext (CCA2) attacks. Since our construction is direct and not based on hierarchical identity-based encryption, it is more efficient than all previously proposed schemes. Furthermore, we give the first chosen-ciphertext secure identity-based key encapsulation mechanism with threshold key delegation and decryption in the standard model.
2006
EPRINT
At CRYPTO 2004, Kurosawa and Desmedt presented a hybrid public-key encryption scheme that is chosen-ciphertext secure in the standard model. Until now it was unknown if the key-encapsulation part of the Kurosawa-Desmedt scheme by itself is still chosen-ciphertext secure or not. In this short note we answer this question to the negative, namely we present a simple chosen-ciphertext attack on the Kurosawa-Desmedt key encapsulation mechanism.
2006
EPRINT
We describe a practical identity-based encryption scheme that is secure in the standard model against chosen-ciphertext (CCA2) attacks. Security is based on an assumption comparable to (but slightly stronger than) Bilinear Decisonal Diffie-Hellman (BDDH). A comparison shows that our construction outperforms all known identity-based encryption schemes in the standard model and its performance is even comparable with the one from the random-oracle based Boneh/Franklin IBE scheme. Our proposed IBE scheme has furthermore the property that it fulfills some notion of redundancy-freeness", i.e. the encryption algorithm is not only a probabilistic injection but also a surjection. As a consequence the ciphertext overhead is nearly optimal: to encrypt $k$ bit messages for $k$ bit identities and with $k$ bit randomness we get $3k$ bit ciphertexts to guarantee (roughly) $k$ bits of security.
2006
EPRINT
The KEM/DEM hybrid encryption paradigm combines the efficiency and large message space of secret key encryption with the advantages of public key cryptography. Due to its simplicity and flexibility, the approach has ever since gained increased popularity and has been successfully adapted in encryption standards. In hybrid public key encryption (PKE), first a key encapsulation mechanism (KEM) is used to fix a random session key that is then fed into a highly efficient data encapsulation mechanism (DEM) to encrypt the actual message. A composition theorem states that if both the KEM and the DEM have the highest level of security (i.e. security against chosen-ciphertext attacks), then so does the hybrid PKE scheme. It is not known if these strong security requirements on the KEM and DEM are also neccessary, nor if such general composition theorems exist for weaker levels of security. In this work we study neccessary and sufficient conditions on the security of the KEM and the DEM in order to guarantee a hybrid PKE scheme with a certain given level of security. More precisely, using nine different security notions for KEMs, ten for DEMs, and six for PKE schemes we completely characterize which combinations lead to a secure hybrid PKE scheme (by proving a composition theorem) and which do not (by providing counterexamples). Furthermore, as an independent result, we revisit and extend prior work on the relation among security notions for KEMs and DEMs.
2006
EPRINT
Designing public key encryption schemes withstanding chosen ciphertext attacks, which is the highest security level for such schemes, is generally perceived as a delicate and intricate task, and for good reason. In the standard model, there are essentially three well-known but quite involved approaches. This state of affairs is to be contrasted with the situation for semantically secure encryption schemes, a much weaker security notion that only guarantees security in the absence of active attack but that appears to be much easier to fulfill, both conceptually and practically. Thus, the boundary between passive attack and active attack seems to make up the dividing line between which security levels are relatively easily achieved and which are not. Our contributions are two-fold. First, we show a simple, efficient black-box construction of a public key encryption scheme withstanding chosen ciphertext attack from any given semantically secure one. Our scheme is $q$-bounded in the sense that security is only guaranteed if the adversary makes at most $q$ adaptive chosen ciphertext queries. Here, $q$ is an arbitrary polynomial that is fixed in advance in the key-generation. Our work thus shows that whether or not the number of active, adversarial queries is known in advance is the dividing line, and not passive versus active attack. In recent work, Gertner, Malkin and Myers show that such black-box reductions are impossible if instead $q$ is a polynomial that only depends on the adversary. Thus, in a sense, our result appears to be the best black-box result one can hope for. Second, we give a non-blackbox reduction from bounded chosen ciphertext security to semantic security where the length of the public/secret keys and ciphertexts drops from quadratic to linear in $q$, compared to our black-box construction. This latter scheme, however, is only of theoretical interest as it uses general NP-reductions, and our blackbox construction is in fact much more practical.
2005
CRYPTO
2005
TCC
2005
EPRINT
In this paper we are interested in efficient and secure constant round multi-party protocols which provide unconditional security against so called honest-but-curious adversaries. In particular, we design a novel constant round protocol that converts from shares over Z_q to shares over the integers working for all shared inputs from Z_q. Furthermore, we present a constant round protocol to securely evaluate a shared input on a public polynomial whose running time is linear in the degree of the polynomial. The proposed solution makes use of Chebyshev Polynomials. We show that the latter two protocols can be used to design efficient constant round protocols for the following natural problems: (i) Equality: Computing shares of the bit indicating if a shared input value equals zero or not. This provides the missing building blocks for many constant round linear algebra protocols from the work of Cramer and Damgaard [CrDa01]. (ii) Comparison: Computing shares of a bit indicating which of two shared inputs is greater. (iii) Bits: Computing shares of the binary representation of a shared input value. (iv) Exponentiation: Computing shares of x^a mod q given shares of x, a and q. Prior to this paper, for all the above mentioned problems, there were in general no efficient constant round protocols known providing unconditional security.
2005
EPRINT
We present a new primitive--Append-only Signatures (AOS)--with the property that any party given an AOS signature aossig[M_1] on message M_1 can compute aossig[M_1||M_2] for any message M_2, where M_1||M_2 is the concatenation of M_1 and M_2. We define the security of AOS, present concrete AOS schemes, and prove their security under standard assumptions. In addition, we find that despite its simple definition, AOS is equivalent to Hierarchical Identity-based Signatures (HIBS) through efficient and security-preserving reductions. Finally, we show direct applications of AOS to problems in network security. Our investigations indicate that AOS is both useful in practical applications and worthy of further study as a cryptographic primitive.
2005
EPRINT
We identify and fill some gaps with regard to consistency (the extent to which false positives are produced) for public-key encryption with keyword search (PEKS). We define computational and statistical relaxations of the existing notion of perfect consistency, show that the scheme of Boneh et al. in Eurocrypt 2004 is computationally consistent, and provide a new scheme that is statistically consistent. We also provide a transform of an anonymous IBE scheme to a secure PEKS scheme that, unlike the previous one, guarantees consistency. Finally, we suggest three extensions of the basic notions considered here, namely anonymous HIBE, public-key encryption with temporary keyword search, and identity-based encryption with keyword search.
2004
EPRINT
In recent years there has been massive progress in the development of technologies for storing and processing of data. If statistical analysis could be applied to such data when it is distributed between several organisations, there could be huge benefits. Unfortunately, in many cases, for legal or commercial reasons, this is not possible. The idea of using the theory of multi-party computation to analyse efficient algorithms for privacy preserving data-mining was proposed by Pinkas and Lindell. The point is that algorithms developed in this way can be used to overcome the apparent impasse described above: the owners of data can, in effect, pool their data while ensuring that privacy is maintained. Motivated by this, we describe how to securely compute the mean of an attribute value in a database that is shared between two parties. We also demonstrate that existing solutions in the literature that could be used to do this leak information, therefore underlining the importance of applying rigorous theoretical analysis rather than settling for ad hoc techniques.

Eurocrypt 2018
Eurocrypt 2017
PKC 2015
Eurocrypt 2015
TCC 2014
PKC 2013
Asiacrypt 2013
Eurocrypt 2013
Asiacrypt 2012
Asiacrypt 2011
PKC 2011
Crypto 2011
PKC 2010
Crypto 2010
PKC 2009
PKC 2008

#### Coauthors

Michel Abdalla (4)
Masayuki Abe (3)
Benedikt Auerbach (2)
Christoph Bader (1)
Mihir Bellare (6)
Olivier Blazy (3)
David Cash (10)
Dario Catalano (3)
Ronald Cramer (5)
Yang Cui (1)
Ivan Damgård (2)
Yevgeniy Dodis (1)
Rafael Dowsley (1)
Léo Ducas (1)
Alex Escala (2)
Sebastian Faust (1)
Serge Fehr (1)
Manuel Fersch (2)
Matthias Fitzi (1)
Matthew K. Franklin (1)
David Freeman (1)
Eduarda S.V. Freire (1)
Georg Fuchsbauer (2)
David Galindo (2)
Romain Gay (1)
Federico Giacon (1)
Oded Goldreich (1)
Goichiro Hanaoka (1)
Kristiyan Haralambiev (2)
Eduard Hauck (1)
Gottfried Herold (2)
Javier Herranz (3)
Felix Heuer (3)
Stefan Heyse (1)
Dennis Hofheinz (20)
Kathrin Hövelmanns (1)
Hideki Imai (2)
Tibor Jager (5)
Abhishek Jain (2)
Saqib A. Kakvi (4)
Tadayoshi Kohno (3)
Tanja Lange (3)
Gregor Leander (2)
Tancrède Lepoint (1)
Yong Li (1)
Julian Loss (3)
Vadim Lyubashevsky (3)
John Malone-Lee (5)
Daniel Masny (3)
Alexander May (1)
Anton Mityagin (1)
Payman Mohassel (2)
Gregory Neven (4)
Jesper Buus Nielsen (1)
Adam O'Neill (3)
Tatsuaki Okamoto (2)
Christof Paar (1)
Carles Padró (1)
Pascal Paillier (3)
Jiaxin Pan (7)
Saurabh Panjwani (1)
Rafael Pass (1)
Kenneth G. Paterson (1)
Chris Peikert (3)
Krzysztof Pietrzak (15)
Bertram Poettering (2)
Carla Ràfols (2)
Barath Raghavan (1)
Alon Rosen (1)
Guy N. Rothblum (1)
Christian Schaffner (1)
Sven Schäge (1)
Peter Schwabe (1)
Gil Segev (1)
Gregor Seiler (1)
Abhi Shelat (1)
Haixia Shi (3)
Victor Shoup (5)
Adam Smith (2)
Martijn Stam (3)
Damien Stehlé (1)
Mario Szegedy (1)
Stefano Tessaro (1)
Tomas Toft (1)
Yevgeniy Vahlis (1)
Vinod Vaikuntanathan (1)
Daniele Venturi (2)
Jorge Luis Villar (2)
Brent Waters (1)
Hoeteck Wee (6)
Enav Weinreb (1)
Daniel Wichs (1)
Moti Yung (3)
Sarah Zakarias (1)
Angela Zottarel (1)