## 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.

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

2015

EPRINT

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

EPRINT

Simple and Efficient Public-Key Encryption from Computational Diffie-Hellman in the Standard Model
Abstract

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

2009

EUROCRYPT

2008

EPRINT

CCA2 Secure IBE: Standard Model Efficiency through Authenticated Symmetric Encryption
Abstract

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

The CCA2-Security of Hybrid Damgård's ElGamal
Abstract

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

A New Randomness Extraction Paradigm for Hybrid Encryption
Abstract

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 1991s Damgaards ElGamal public-key encryption
scheme under the DDH assumption.

2008

JOFC

2008

EPRINT

The Twin Diffie-Hellman Problem and Applications
Abstract

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 Hellmans 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.

2007

CRYPTO

2007

EPRINT

From Selective-ID to Full Security: The Case of the Inversion-Based Boneh-Boyen IBE Scheme
Abstract

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

Efficient Hybrid Encryption from ID-Based Encryption
Abstract

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

Chosen-Ciphertext Secure Key-Encapsulation Based on Gap Hashed Diffie-Hellman
Abstract

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

Generalized Key Delegation for Hierarchical Identity-Based Encryption
Abstract

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

Secure Hybrid Encryption from Weakened Key Encapsulation
Abstract

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

EPRINT

Direct Chosen-Ciphertext Secure Identity-Based Key Encapsulation without Random Oracles
Abstract

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

The Kurosawa-Desmedt Key Encapsulation is not Chosen-Ciphertext Secure
Abstract

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

Chosen-Ciphertext Secure Identity-Based Encryption in the Standard Model with short Ciphertexts
Abstract

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

KEM/DEM: Necessary and Sufficient Conditions for Secure Hybrid Encryption
Abstract

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

A Note on Bounded Chosen Ciphertext Security from Black-box Semantical Security
Abstract

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

EPRINT

Unconditionally Secure Constant Round Multi-Party Computation for Equality, Comparison, Bits and Exponentiation
Abstract

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

Append-Only Signatures
Abstract

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

Searchable Encryption Revisited: Consistency Properties, Relation to Anonymous IBE, and Extensions
Abstract

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

Secure Computation of the Mean and Related Statistics
Abstract

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.

#### 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 (4)
- Masayuki Abe (3)
- Joël Alwen (1)
- Benedikt Auerbach (3)
- Christoph Bader (1)
- Mihir Bellare (6)
- Bruno Blanchet (1)
- 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 (2)
- Oded Goldreich (1)
- Shuai Han (1)
- Goichiro Hanaoka (1)
- Kristiyan Haralambiev (2)
- Eduard Hauck (3)
- Gottfried Herold (2)
- Javier Herranz (3)
- Felix Heuer (3)
- Stefan Heyse (1)
- Dennis Hofheinz (20)
- Kathrin Hövelmanns (2)
- Hideki Imai (2)
- Tibor Jager (7)
- Abhishek Jain (2)
- Saqib A. Kakvi (4)
- Tadayoshi Kohno (3)
- Tanja Lange (3)
- Gregor Leander (2)
- Tancrède Lepoint (1)
- Yong Li (1)
- Benjamin Lipp (1)
- Shengli Liu (1)
- Julian Loss (4)
- Vadim Lyubashevsky (3)
- John Malone-Lee (5)
- Daniel Masny (3)
- Alexander May (1)
- Anton Mityagin (1)
- Payman Mohassel (2)
- Gregory Neven (4)
- Ngoc Khanh Nguyen (1)
- Jesper Buus Nielsen (1)
- Adam O'Neill (3)
- Tatsuaki Okamoto (2)
- Christof Paar (1)
- Carles Padró (1)
- Pascal Paillier (3)
- Jiaxin Pan (8)
- 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)
- Doreen Riepel (3)
- Alon Rosen (1)
- Guy N. Rothblum (1)
- Christian Schaffner (1)
- Sven Schäge (4)
- 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)
- Dominique Unruh (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)