## CryptoDB

### Eike Kiltz

#### Publications

**Year**

**Venue**

**Title**

2021

EUROCRYPT

Tightly-Secure Authenticated Key Exchange, Revisited
📺
Abstract

We introduce new tightly-secure authenticated key exchange (AKE) protocols that are extremely efficient, yet have only a constant security loss and can be instantiated in the random oracle model both from the standard DDH assumption and a subgroup assumption over RSA groups. These protocols can be deployed with optimal parameters, independent of the number of users or sessions, without the need to compensate a security loss with increased parameters and thus decreased computational efficiency.
We use the standard “Single-Bit-Guess” AKE security (with forward secrecy and state corruption) requiring all challenge keys to be simultaneously pseudo-random. In contrast, most previous papers on tightly secure AKE protocols (Bader et al., TCC 2015; Gjøsteen and Jager, CRYPTO 2018; Liu et al., ASIACRYPT 2020) concentrated on a non-standard “Multi-Bit-Guess” AKE security which is known not to compose tightly with symmetric primitives to build a secure communication channel.
Our key technical contribution is a new generic approach to construct tightly-secure AKE protocols based on non-committing key encapsulation mechanisms. The resulting DDH-based protocols are considerably more efficient than all previous constructions.

2021

EUROCRYPT

Analysing the HPKE Standard
📺
Abstract

The Hybrid Public Key Encryption (HPKE) scheme is an emerging standard currently under consideration by the Crypto Forum Research Group (CFRG) of the IETF as a candidate for formal approval. Of the four modes of HPKE, we analyse the authenticated mode HPKE_Auth in its single-shot encryption form as it contains what is, arguably, the most novel part of HPKE.
HPKE_Auth’s intended application domain is captured by a new primitive which we call Authenticated Public Key Encryption (APKE). We provide syntax and security definitions for APKE schemes, as well as for the related Authenticated Key Encapsulation Mechanisms (AKEMs). We prove security of the AKEM scheme DH-AKEM underlying HPKE Auth based on the Gap Diffie-Hellman assumption and provide general AKEM/DEM composition theorems with which to argue about HPKE_Auth’s security. To this end, we also formally analyse HPKE_Auth’s key schedule and key derivation functions. To increase confidence in our results we use the automatic theorem proving tool CryptoVerif. All our bounds are quantitative and
we discuss their practical implications for HPKE_Auth.
As an independent contribution we propose the new framework of nominal groups that allows us to capture abstract syntactical and security properties of practical elliptic curves, including the Curve25519 and Curve448 based groups (which do not constitute cyclic groups).

2021

CRYPTO

Authenticated Key Exchange and Signatures with Tight Security in the Standard Model
📺
Abstract

We construct the first authenticated key exchange protocols that achieve tight security in the standard model. Previous works either relied on techniques that seem to inherently require a random oracle, or achieved only “Multi-Bit-Guess” security, which is not known to compose tightly, for instance, to build a secure channel.
Our constructions are generic, based on digital signatures and key encapsulation mechanisms (KEMs). The main technical challenges we resolve is to determine suitable KEM security notions which on the one hand are strong enough to yield tight security, but at the same time weak enough to be efficiently instantiable in the standard model, based on standard techniques such as universal hash proof systems.
Digital signature schemes with tight multi-user security in presence of adaptive corruptions are a central building block, which is used in all known constructions of tightly-secure AKE with full forward security. We identify a subtle gap in the security proof of the only previously known efficient standard model scheme by Bader et al. (TCC 2015). We develop a new variant, which yields the currently most efficient signature scheme that achieves this strong security notion without random oracles and based on standard hardness assumptions.

2021

PKC

How Provably Secure are (EC)DSA Signatures?
📺 ★
Abstract

Today, digital signatures are an omnipresent cryptographic primitive. They are extensively used for message and entity authentication and find widespread application in real-world protocols. Without much doubt, the specific schemes deployed most often are the RSA-based PKCS#1 v1.5, and the discrete logarithm-based DSA and ECDSA. For instance, current versions of TLS - the standard technology for securing internet connections - exclusively employ signatures of these types to authenticate servers. Furthermore, most cryptocurrencies like Bitcoin and Ethereum use ECDSA for signing transactions. The popularity of (EC)DSA signatures stands in stark contrast to the absence of rigorous security analyses. In this talk we will survey known provable security results about DSA and ECDSA. We will also discuss limitations of current provable security approaches.

2021

TCC

On the Impossibility of Purely Algebraic Signatures
📺
Abstract

The existence of one-way functions implies secure digital sig- natures, but not public-key encryption (at least in a black-box setting). Somewhat surprisingly, though, efficient public-key encryption schemes appear to be much easier to construct from concrete algebraic assumptions (such as the factoring of Diffie-Hellman-like assumptions) than efficient digital signature schemes. In this work, we provide one reason for this apparent difficulty to construct efficient signature schemes. Specifically, we prove that a wide range of algebraic signature schemes (in which verification essentially checks a number of linear equations over a group) fall to conceptually surprisingly simple linear algebra attacks. In fact, we prove that in an algebraic signature scheme, sufficiently many signatures can be linearly combined to a signature of a fresh message. We present attacks both in known-order and hidden-order groups (although in hidden-order settings, we have to restrict our definition of algebraic signatures a little). More explicitly, we show:
– the insecurity of all algebraic signature schemes in Maurer’s generic group model, as long as the signature schemes do not rely on other cryptographic assumptions, such as hash functions.
– the insecurity of a natural class of signatures in hidden-order groups, where verification consists of linear equations over group elements.
We believe that this highlights the crucial role of public verifiability in digital signature schemes. Namely, while public-key encryption schemes do not require any publicly verifiable structure on ciphertexts, it is exactly this structure on signatures that invites attacks like ours and makes it hard to construct efficient signatures.

2020

EUROCRYPT

Everybody’s a Target: Scalability in Public-Key Encryption
📺
Abstract

For 1<=m<=n, we consider a natural m-out-of-n multi-instance scenario for a public-key encryption (PKE) scheme. An adversary, given n independent instances of PKE, wins if he breaks at least m out of the n instances. In this work, we are interested in the scaling factor of PKE schemes, SF, which measures how well the difficulty of breaking m out of the n instances scales in m. That is, a scaling factor SF=l indicates that breaking m out of n instances is at least l times more difficult than breaking one single instance. A PKE scheme with small scaling factor hence provides an ideal target for mass surveillance. In fact, the Logjam attack (CCS 2015) implicitly exploited, among other things, an almost constant scaling factor of ElGamal over finite fields (with shared group parameters).
For Hashed ElGamal over elliptic curves, we use the generic group model to describe how the scaling factor depends on the scheme's granularity. In low granularity, meaning each public key contains its independent group parameter, the scheme has optimal scaling factor SF=m; In medium and high granularity, meaning all public keys share the same group parameter, the scheme still has a reasonable scaling factor SF=sqrt(m). Our findings underline that instantiating ElGamal over elliptic curves should be preferred to finite fields in a multi-instance scenario.
As our main technical contribution, we derive new generic-group lower bounds of Omega(sqrt(mp)) on the complexity of solving both the m-out-of-n Gap Discrete Logarithm and the m-out-of-n Gap Computational Diffie-Hellman problem over groups of prime order p, extending a recent result by Yun (EUROCRYPT 2015). We establish the lower bound by studying the hardness of a related computational problem which we call the search-by-hypersurface problem.

2020

PKC

Generic Authenticated Key Exchange in the Quantum Random Oracle Model
📺
Abstract

We propose $$mathsf {FO_mathsf {AKE}}$$ , a generic construction of two-message authenticated key exchange (AKE) from any passively secure public key encryption (PKE) in the quantum random oracle model (QROM). Whereas previous AKE constructions relied on a Diffie-Hellman key exchange or required the underlying PKE scheme to be perfectly correct, our transformation allows arbitrary PKE schemes with non-perfect correctness. Dealing with imperfect schemes is one of the major difficulties in a setting involving active attacks. Our direct construction, when applied to schemes such as the submissions to the recent NIST post-quantum competition, is more natural than previous AKE transformations. Furthermore, we avoid the use of (quantum-secure) digital signature schemes which are considerably less efficient than their PKE counterparts. As a consequence, we can instantiate our AKE transformation with any of the submissions to the recent NIST competition, e.g., ones based on codes and lattices. $$mathsf {FO_mathsf {AKE}}$$ can be seen as a generalisation of the well known Fujisaki-Okamoto transformation (for building actively secure PKE from passively secure PKE) to the AKE setting. As a helper result, we also provide a security proof for the Fujisaki-Okamoto transformation in the QROM for PKE with non-perfect correctness which is tighter and tolerates a larger correctness error than previous proofs.

2020

CRYPTO

Lattice-Based Blind Signatures, Revisited
📺
Abstract

We observe that all previously known lattice-based blind signatures schemes contain subtle flaws in their security proofs (e.g.,~Rückert, ASIACRYPT '08) or can be attacked (e.g., BLAZE by Alkadri et al., FC~'20). Motivated by this, we revisit the problem of constructing blind signatures from standard lattice assumptions. We propose a new three-round lattice-based blind signature scheme whose security can be proved, in the random oracle model, from the standard SIS assumption. Our starting point is a modified version of the insecure three-round BLAZE scheme, which itself is based Lyubashevsky's three-round identification scheme combined with a new aborting technique to reduce the correctness error. Our proof builds upon and extends the recent modular framework for blind signatures of Hauck, Kiltz, and Loss (EUROCRYPT~'19). It also introduces several new techniques to overcome the additional challenges posed by the correctness error which is inherent to all lattice-based constructions.
While our construction is mostly of theoretical interest, we believe it to be an important stepping stone for future works in this area.

2019

EUROCRYPT

A Modular Treatment of Blind Signatures from Identification Schemes
📺
Abstract

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

CRYPTO

The Algebraic Group Model and its Applications
📺
Abstract

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

Public-Key Encryption Resistant to Parameter Subversion and Its Realization from Efficiently-Embeddable Groups
Abstract

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

Hybrid Encryption in a Multi-user Setting, Revisited
Abstract

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

CRYSTALS-Dilithium: A Lattice-Based Digital Signature Scheme
Abstract

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.

2015

JOFC

2013

CRYPTO

2012

JOFC

Bonsai Trees, or How to Delegate a Lattice Basis
Abstract

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

Programmable Hash Functions and Their Applications
Abstract

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.

2010

PKC

2009

EUROCRYPT

2008

JOFC

2007

CRYPTO

2005

CRYPTO

#### Program Committees

- Crypto 2020
- TCC 2019
- 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 (2)
- Masayuki Abe (2)
- Joël Alwen (1)
- Benedikt Auerbach (3)
- Christoph Bader (1)
- Mihir Bellare (5)
- Bruno Blanchet (1)
- Olivier Blazy (2)
- David Cash (9)
- Dario Catalano (2)
- Ronald Cramer (4)
- Ivan Damgård (2)
- Yevgeniy Dodis (1)
- Nico Döttling (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 (1)
- Romain Gay (1)
- Federico Giacon (2)
- Oded Goldreich (1)
- Shuai Han (1)
- Goichiro Hanaoka (1)
- Kristiyan Haralambiev (1)
- Dominik Hartmann (1)
- Eduard Hauck (3)
- Gottfried Herold (2)
- Javier Herranz (1)
- Felix Heuer (2)
- Stefan Heyse (1)
- Dennis Hofheinz (17)
- Kathrin Hövelmanns (2)
- Hideki Imai (1)
- Tibor Jager (6)
- Abhishek Jain (2)
- Saqib A. Kakvi (4)
- Tadayoshi Kohno (2)
- Tanja Lange (2)
- Gregor Leander (1)
- Tancrède Lepoint (1)
- Yong Li (1)
- Benjamin Lipp (1)
- Shengli Liu (1)
- Julian Loss (4)
- Vadim Lyubashevsky (3)
- John Malone-Lee (3)
- Daniel Masny (2)
- Alexander May (1)
- Payman Mohassel (2)
- Gregory Neven (2)
- Ngoc Khanh Nguyen (1)
- Jesper Buus Nielsen (1)
- Adam O'Neill (3)
- Tatsuaki Okamoto (2)
- Christof Paar (1)
- Carles Padró (1)
- Pascal Paillier (2)
- Jiaxin Pan (6)
- Rafael Pass (1)
- Kenneth G. Paterson (1)
- Chris Peikert (3)
- Krzysztof Pietrzak (11)
- Bertram Poettering (2)
- Carla Ràfols (2)
- Doreen Riepel (3)
- Alon Rosen (1)
- Guy N. Rothblum (1)
- Christian Schaffner (1)
- Sven Schäge (5)
- Peter Schwabe (1)
- Gil Segev (1)
- Gregor Seiler (1)
- Abhi Shelat (1)
- Haixia Shi (2)
- Victor Shoup (3)
- Adam Smith (2)
- Martijn Stam (1)
- Damien Stehlé (1)
- Mario Szegedy (1)
- Stefano Tessaro (1)
- Tomas Toft (1)
- Dominique Unruh (1)
- Bogdan Ursu (1)
- Vinod Vaikuntanathan (1)
- Daniele Venturi (2)
- Jorge Luis Villar (2)
- Brent Waters (1)
- Hoeteck Wee (4)
- Enav Weinreb (1)
- Daniel Wichs (1)
- Moti Yung (1)
- Sarah Zakarias (1)
- Angela Zottarel (1)