## CryptoDB

### Mihir Bellare

#### Publications

**Year**

**Venue**

**Title**

2021

ASIACRYPT

Chain Reductions for Multi-Signatures and the HBMS Scheme
Abstract

Existing proofs for existing Discrete Log (DL) based multi-signature schemes give only weak guarantees if the schemes are implemented, as they are in practice, in 256-bit groups. This is because the underlying reductions, which are mostly in the standard model and from DL, are loose. We show that relaxing either the model or the assumption suffices to obtain tight reductions. Namely we give (1) tight proofs from DL in the Algebraic Group Model, and (2) tight, standard-model proofs from well-founded assumptions other than DL. We first do this for the classical 3-round schemes, namely $\BN$ and $\MuSig$. Then we give a new 2-round multi-signature scheme, $\MSB$, as efficient as prior ones, for which we do the same. These multiple paths to security for a single scheme are made possible by a framework of chain reductions, in which a reduction is broken into a chain of sub-reductions involving intermediate problems. Overall our results improve the security guarantees for DL-based multi-signature schemes in the groups in which they are implemented in practice.

2020

EUROCRYPT

Security under Message-Derived Keys: Signcryption in iMessage
📺
Abstract

At the core of Apple's iMessage is a SignCryption scheme that involves symmetric encryption of a message under a key that is derived from the message itself. To capture this, we formalize a primitive we call Encryption under Message-Derived Keys (EMDK). We prove security of the EMDK scheme underlying iMessage. We use this to prove security of the SignCryption scheme itself, with respect to definitions of SignCryption we give that enhance prior ones to cover issues peculiar to messaging protocols. Our provable-security results are quantitative, and we discuss the practical implications for iMessage.

2020

EUROCRYPT

Separate Your Domains: NIST PQC KEMs, Oracle Cloning and Read-Only Indifferentiability
📺
Abstract

It is convenient and common for schemes in the random oracle model to assume access to multiple random oracles (ROs), leaving to implementations the task --we call it oracle cloning-- of constructing them from a single RO. The first part of the paper is a case study of oracle cloning in KEM submissions to the NIST Post-Quantum Cryptography standardization process. We give key-recovery attacks on some submissions arising from mistakes in oracle cloning, and find other submissions using oracle cloning methods whose validity is unclear. Motivated by this, the second part of the paper gives a theoretical treatment of oracle cloning. We give a definition of what is an "oracle cloning method" and what it means for such a method to "work," in a framework we call read-only indifferentiability, a simple variant of classical indifferentiability that yields security not only for usage in single-stage games but also in multi-stage ones. We formalize domain separation, and specify and study many oracle cloning methods, including common domain-separating ones, giving some general results to justify (prove read-only indifferentiability of) certain classes of methods. We are not only able to validate the oracle cloning methods used in many of the unbroken NIST PQC KEMs, but also able to specify and validate oracle cloning methods that may be useful beyond that.

2019

CRYPTO

Nonces Are Noticed: AEAD Revisited
📺
Abstract

We draw attention to a gap between theory and usage of nonce-based symmetric encryption, under which the way the former treats nonces can result in violation of privacy in the latter. We bridge the gap with a new treatment of nonce-based symmetric encryption that modifies the syntax (decryption no longer takes a nonce), upgrades the security goal (asking that not just messages, but also nonces, be hidden) and gives simple, efficient schemes conforming to the new definitions. We investigate both basic security (holding when nonces are not reused) and advanced security (misuse resistance, providing best-possible guarantees when nonces are reused).

2019

ASIACRYPT

The Local Forking Lemma and Its Application to Deterministic Encryption
Abstract

We bypass impossibility results for the deterministic encryption of public-key-dependent messages, showing that, in this setting, the classical Encrypt-with-Hash scheme provides message-recovery security, across a broad range of message distributions. The proof relies on a new variant of the forking lemma in which the random oracle is reprogrammed on just a single fork point rather than on all points past the fork.

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.

2015

JOFC

2015

EPRINT

2015

EUROCRYPT

2014

ASIACRYPT

2012

ASIACRYPT

2012

JOFC

On-line Ciphers and the Hash-CBC Constructions
Abstract

We initiate a study of on-line ciphers. These are ciphers that can take input plaintexts of large and varying lengths and will output the i th block of the ciphertext after having processed only the first i blocks of the plaintext. Such ciphers permit length-preserving encryption of a data stream with only a single pass through the data. We provide security definitions for this primitive and study its basic properties. We then provide attacks on some possible candidates, including CBC with fixed IV. We then provide two constructions, HCBC1 and HCBC2, based on a given block cipher E and a family of computationally AXU functions. HCBC1 is proven secure against chosen-plaintext attacks assuming that E is a PRP secure against chosen-plaintext attacks, while HCBC2 is proven secure against chosen-ciphertext attacks assuming that E is a PRP secure against chosen-ciphertext attacks.

2010

EPRINT

Cryptographic Agility and its Relation to Circular Encryption
Abstract

We initiate a provable-security treatment of cryptographic \emph{agility}. A primitive (for example PRFs, authenticated encryption schemes or digital signatures) is agile when multiple, individually secure schemes can securely share the same key. We provide a surprising connection between two seemingly unrelated but challenging questions. The first, new to this paper, is whether wPRFs (weak-PRFs) are agile. The second, already posed several times in the literature, is whether every secure (IND-R) encryption scheme is secure when encrypting cycles. We resolve the second question in the negative and thereby the first as well. We go on to provide a comprehensive treatment of agility, with definitions for various different primitives. We explain the practical motivations for agility. We provide foundational results that show to what extent it is achievable and practical constructions to achieve it to the best extent
possible. On the theoretical side our work uncovers new notions and relations and settles stated open questions, and on the practical side it serves to guide developers.

2010

EPRINT

Identity-Based Encryption Secure under Selective Opening Attack
Abstract

We present the first Identity-Based Encryption (IBE) scheme that is proven secure against
selective opening attack (SOA). This means that if an adversary, given a vector of ciphertexts, adaptively
corrupts some fraction of the senders, exposing not only their messages but also their coins, the privacy
of the unopened messages is guaranteed. Achieving security against such attacks is well-known to be
challenging and was only recently solved in the PKE case via lossy encryption. We explain why those
methods wont work for IBE and instead rely on an approach based on encryption schemes that have a
property we call one-sided public openability. Our SOA-secure IBE scheme is quite efficient and proven
secure without random oracles based on the Decision Linear assumption.

2010

EPRINT

Pseudorandom Functions and Permutations Provably Secure Against Related-Key Attacks
Abstract

This paper fills an important foundational gap with the first proofs, under standard assumptions and in the standard model, of the existence of pseudorandom functions (PRFs) and pseudorandom permutations (PRPs) resisting rich and relevant forms of related-key attacks (RKA). An RKA allows the adversary to query the function not only under the target key but under other keys derived from it in adversary-specified ways. Based on the Naor-Reingold PRF we obtain an RKA-PRF whose keyspace is a group and that is proven, under DDH, to resist attacks in which the key may be operated on by arbitrary adversary-specified group elements. Previous work was able only to provide schemes in idealized models (ideal cipher, random oracle), under new, non-standard assumptions, or for limited classes of attacks. The reason was technical difficulties that we resolve via a new approach and framework that, in addition to the above, yields other RKA-PRFs including a DLIN-based one derived from the Lewko-Waters PRF. Over the last 15 years cryptanalysts and blockcipher designers have routinely and consistently targeted RKA-security; it is visibly important for abuse-resistant cryptography; and it helps protect against fault-injection sidechannel attacks. Yet ours are the first significant proofs of existence of secure constructs. We warn that our constructs are proofs-of-concept in the foundational style and not practical.

2009

EUROCRYPT

2009

EUROCRYPT

2009

EPRINT

Encryption Schemes Secure under Selective Opening Attack
Abstract

The existence of encryption schemes secure under selective opening attack (SOA) has remained open despite considerable interest and attention. We provide the first public key encryption schemes secure against sender corruptions in this setting. The underlying tool is lossy encryption. The schemes have short keys. (Public and secret keys of a fixed length suffice for encrypting an arbitrary number of messages.) The schemes are stateless and noninteractive, and security does not rely on erasures. The schemes are without random oracles, proven secure under standard assumptions (DDH, Pailliers DCR, QR, lattices), and even efficient. We are able to meet both an indistinguishability (IND-SO-ENC) and a simulation-style, semantic security (SEM-SO-ENC) definition.

2009

EPRINT

Simulation without the Artificial Abort: Simplified Proof and Improved Concrete Security for Waters' IBE Scheme
Abstract

Waters' variant of the Boneh-Boyen IBE scheme is attractive because of its efficency, applications, and security attributes,but suffers from a relatively complex proof with poor concrete security. This is due in part to the proof's ``artificial abort'' step, which has then been inherited by numerous derivative works. It has often been asked whether this step is necessary. We show that it is not, providing a new proof
that eliminates this step. The new proof is not only simpler than the original one but offers better concrete security for important ranges of
the parameters. As a result, one can securely use smaller groups, resulting in significant efficiency improvements.

2009

EPRINT

Key Insulation and Intrusion Resilience Over a Public Channel
Abstract

Key insulation (KI) and Intrusion resilience (IR) are methods to protect a
user's key against exposure by utilizing periodic communications with an
auxiliary helper. But existing work assumes a secure channel between user and
helper. If we want to realize KI or IR in practice we must realize this secure channel. This paper looks at the question of how to do this when the communication is over what we are more likely to have in practice, namely a public channel such
as the Internet or a wireless network. We explain why this problem is not trivial, introduce models and definitions that capture the
desired security in a public channel setting, and provide a complete (and
surprising) answer to the question of when KI and IR are possible over a
public channel. The information we provide is important to guide
practitioners with regard to the usage of KI and IR and also to guide future
research in this area.

2008

JOFC

2008

JOFC

2008

CRYPTO

2008

EPRINT

Deterministic Encryption: Definitional Equivalences and Constructions without Random Oracles
Abstract

We strengthen the foundations of deterministic public-key encryption via definitional equivalences and standard-model constructs based on general assumptions. Specifically we consider seven notions of privacy for deterministic encryption, including six forms of semantic security and an indistinguishability notion, and show them all equivalent. We then present a deterministic scheme for the secure encryption of uniformly and independently distributed messages based solely on the existence of
trapdoor one-way permutations. We show a generalization of the construction that allows secure deterministic encryption of independent high-entropy messages. Finally we show relations between deterministic and standard (randomized) encryption.

2008

EPRINT

Hash Functions from Sigma Protocols and Improvements to VSH
Abstract

We present a general way to get a provably collision-resistant
hash function from any (suitable) $\Sigma$-protocol.
This enables us to both get new designs and to unify and improve
previous work. In the first category, we obtain, via a modified
version of the Fiat-Shamir protocol, the fastest known hash function
that is provably collision-resistant based on the \textit{standard}
factoring assumption. In the second category, we
provide a modified version VSH^* of
VSH which is faster when hashing short messages.
(Most Internet packets are short.) We also show that $\Sigma$-hash
functions are chameleon, thereby
obtaining several new and efficient chameleon hash functions with
applications to on-line/off-line signing, chameleon signatures and
designated-verifier signatures.

2007

PKC

2007

EPRINT

On-Line Ciphers and the Hash-CBC Constructions
Abstract

We initiate a study of on-line ciphers. These are ciphers that can take input plaintexts of large and varying lengths and will output the i-th block of the ciphertext after having processed only the first i blocks of the plaintext. Such ciphers permit length-preserving encryption of a data stream with only a single pass through the data. We provide security definitions for this primitive and study its basic properties. We then provide attacks on some possible candidates, including CBC with fixed IV. We then provide two constructions, HCBC1 and HCBC2, based on a given block cipher E and a family of computationally AXU functions. HCBC1 is proven secure against chosen-plaintext attacks assuming that E is a PRP secure against chosen-plaintext attacks, while HCBC2 is proven secure against chosen-ciphertext attacks assuming that E is a PRP secure against chosen-ciphertext attacks.

2007

EPRINT

Hash Functions in the Dedicated-Key Setting: Design Choices and MPP Transforms
Abstract

In the dedicated-key setting, one starts with a compression function f:{0,1}^k x {0,1}^{n+d} -> {0,1}^n and builds a family of hash functions H^f:K x M -> {0,1}^n indexed by a key space K. This is different from the more traditional design approach used to build hash functions such as MD5 or SHA-1, in which compression functions and hash functions do not have dedicated key inputs. We explore the benefits and drawbacks of building hash functions in the dedicated-key setting (as compared to the more traditional approach), highlighting several unique features of the former. Should one choose to build hash functions in the dedicated-key setting, we suggest utilizing multi-property-preserving (MPP) domain extension transforms. We analyze seven existing dedicated-key transforms with regard to the MPP goal and propose two simple new MPP transforms.

2007

EPRINT

Two-Tier Signatures, Strongly Unforgeable Signatures, and Fiat-Shamir without Random Oracles
Abstract

We provide a positive result about the Fiat-Shamir (FS) transform in the standard model, showing how to use it to convert three-move identification protocols into two-tier signature schemes with a proof of security that makes a standard assumption on the hash function rather than modeling it as a random oracle. The result requires security of the starting protocol against concurrent attacks. We can show that numerous protocols have the required properties and so obtain numerous efficient two-tier schemes. Our first application is a two-tier scheme based efficient transform of any unforgeable signature scheme into a strongly unforgeable one. (This extends Boneh, Shen and Waters [BSW06] whose transform only applies to a limited class of schemes.) The second application is new one-time signature schemes that, compared to one-way function based ones of the same computational cost, have smaller key and signature sizes.

2006

EPRINT

On Probabilistic versus Deterministic Provers in the Definition of Proofs Of Knowledge
Abstract

This note points out a gap between two natural formulations of
the concept of a proof of knowledge, and shows that in all
natural cases (e.g., NP-statements) this gap can be closed.
The aforementioned formulations differ by whether they refer to
(all possible) probabilistic or deterministic prover strategies.
Unlike in the rest of cryptography, in the current context,
the obvious transformation of probabilistic strategies
to deterministic strategies does not seem to suffice per se.

2006

EPRINT

New Proofs for NMAC and HMAC: Security Without Collision-Resistance
Abstract

HMAC was proved by Bellare, Canetti and Krawczyk [2] to be a PRF assuming that (1)
the underlying compression function is a PRF, and (2) the iterated hash
function is weakly collision-resistant.
However, recent attacks show that assumption (2) is false for
MD5 and SHA-1,
removing the proof-based support for HMAC in these cases.
This paper proves that HMAC is a PRF
under the sole assumption that the compression function is a PRF. This recovers
a proof based guarantee since no known attacks compromise the pseudorandomness
of the compression function, and it also helps explain the resistance-to-attack
that HMAC has shown even when implemented with hash functions whose
(weak) collision resistance is compromised. We also show that an even
weaker-than-PRF condition on the compression function, namely that it is a
privacy-preserving MAC, suffices to establish HMAC is a MAC as long as the hash
function meets the very weak requirement of being computationally almost
universal, where again the value lies in the fact that known attacks do not
invalidate the assumptions made.

2006

EPRINT

Deterministic and Efficiently Searchable Encryption
Abstract

We present as-strong-as-possible definitions of privacy, and constructions achieving them, for public-key encryption schemes where the encryption algorithm is \textit{deterministic}. We obtain as a consequence database encryption methods that permit fast (i.e.~sub-linear, and in fact logarithmic, time) search while provably providing privacy that is as strong as possible subject to this fast search constraint. One of our constructs, called RSA-DOAEP, has the added feature of being length preserving, so that it is the first example of a public-key cipher. We generalize this to obtain a notion of efficiently-searchable encryption schemes which permit more flexible privacy to search-time trade-offs via a technique called bucketization. Our results answer much-asked questions in the database community and provide foundations for work done there.

2006

EPRINT

Non-Malleable Encryption: Equivalence between Two Notions, and an Indistinguishability-based Characterization
Abstract

We prove the equivalence of two definitions of non-malleable
encryption, one based on the simulation approach of Dolev, Dwork and Naor and the other based on the comparison approach of Bellare,
Desai, Pointcheval and Rogaway.
Our definitions are slightly stronger than the original ones.
The equivalence relies on a new
characterization of non-malleable encryption in terms of the standard
notion of indistinguishability of Goldwasser and Micali. We show that
non-malleability is equivalent to indistinguishability under a
``parallel chosen ciphertext attack,'' this being a new kind of chosen
ciphertext attack we introduce, in which the adversary's decryption
queries are not allowed to depend on answers to previous queries, but
must be made all at once. This characterization simplifies both the
notion of non-malleable encryption and its usage, and enables one to
see more easily how it compares with other notions of encryption. The
results here apply to non-malleable encryption under any form of
attack, whether chosen-plaintext, chosen-ciphertext, or adaptive
chosen-ciphertext.

2006

EPRINT

Stateful Public-Key Cryptosystems: How to Encrypt with One 160-bit Exponentiation
Abstract

We show how to significantly speed-up the encryption portion
of some public-key cryptosystems by the simple expedient of allowing a
sender to maintain state that is re-used across different encryptions.
In particular we present stateful versions of the DHIES and
Kurosawa-Desmedt schemes that each use only one exponentiation to
encrypt, as opposed to two and three respectively in the original
schemes, yielding the fastest discrete-log based public-key encryption
schemes known in the random-oracle and standard models respectively.
The schemes are proven to meet an appropriate extension of the
standard definition of IND-CCA security that takes into account novel
types of attacks possible in the stateful setting.

2006

EPRINT

Unrestricted Aggregate Signatures
Abstract

Secure use of the BGLS aggregate signature schemes is restricted to the aggregation of distinct messages (for the basic scheme) or per-signer distinct messages (for the enhanced, prepend-public-key version of the scheme). We argue that these restrictions preclude interesting applications, make usage of the schemes error-prone and are generally undesirable in practice. Via a new analysis and proof, we show how the restrictions can be lifted, yielding the first truly unrestricted aggregate signature scheme. Via another new analysis and proof, we show that the distinct signer restriction on the sequential aggregate signature schemes of Lysyanskaya et al. can also be dropped, yielding an unrestricted sequential aggregate signature scheme. Finally, we present variants of these schemes with tight security reductions.

2006

EPRINT

Multi-Property-Preserving Hash Domain Extension and the EMD Transform
Abstract

We point out that the seemingly strong pseudorandom oracle preserving (PRO-Pr) property of hash function domain-extension transforms defined and implemented by Coron et. al. [12] can actually weaken our guarantees on the hash function, in particular producing a hash function that fails to be even collision-resistant (CR) even though the compression function to which the transform is applied is CR. Not only is this true in general, but we show that all the transforms presented in [12] have this weakness. We suggest that the appropriate goal of a domain extension transform for the next generation of hash functions is to be multi-property preserving, namely that one should have a single transform that is simultaneously at least collision-resistance preserving, pseudorandom function preserving and PRO-Pr. We present an efficient new transform that is proven to be multi-property preserving in this sense.

2006

EPRINT

Robust Computational Secret Sharing and a Unified Account of Classical Secret-Sharing Goals
Abstract

We give a unified account of classical secret-sharing goals from a modern cryptographic vantage. Our treatment encompasses perfect, statistical, and computational secret sharing; static and dynamic adversaries; schemes with or without robustness; schemes where a participant recovers the secret and those where an external party does so. We then show that Krawczyk's 1993 protocol for robust computational secret sharing (RCSS) need not be secure, even in the random-oracle model and for threshold schemes, if the encryption primitive it uses satisfies only one-query indistinguishability (ind1), the only notion Krawczyk defines. Nonetheless, we show that the protocol is secure (in the random-oracle model, for threshold schemes) if the encryption scheme also satisfies one-query key-unrecoverability (key1). Since practical encryption schemes are ind1+key1 secure, our result effectively shows that Krawczyk's RCSS protocol is sound (in the random-oracle model, for threshold schemes). Finally, we prove the security for a variant of Krawczyk's protocol, in the standard model and for arbitrary access structures, assuming ind1 encryption and a statistically-hiding, weakly-binding commitment scheme.

2005

CRYPTO

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

The Knowledge-of-Exponent Assumptions and 3-Round Zero-Knowledge Protocols
Abstract

Hada and Tanaka showed the existence
of 3-round, negligible-error zero-knowledge arguments for NP based
on a pair of non-standard assumptions, here called KEA1 and
KEA2. In this paper we show that KEA2 is false. This renders vacuous
the results of Hada and Tanaka. We recover these results, however,
under a suitably modified new assumption called KEA3. What we
believe is most interesting is that we show that it is possible to
``falsify'' assumptions like KEA2 that, due to their nature and
quantifier-structure, do not lend themselves easily to ``efficient
falsification'' (Naor).

2004

EPRINT

Towards Plaintext-Aware Public-Key Encryption without Random Oracles
Abstract

We consider the problem of defining and
achieving plaintext-aware encryption without random oracles in the classical
public-key model. We provide definitions for a hierarchy of notions of
increasing strength: PA0, PA1 and PA2, chosen so that PA1+IND-CPA =>
IND-CCA1 and PA2+IND-CPA => IND-CCA2. Towards achieving the new
notions of plaintext awareness, we show that a scheme due to Damgard,
denoted DEG, and the ``lite'' version of the Cramer-Shoup scheme,
denoted CSL, are both PA0 under the KEA0
assumption of Damgard, and PA1 under an extension of this assumption called
KEA1. As a result, DEG is the most efficient proven IND-CCA1 scheme known.

2004

EPRINT

Foundations of Group Signatures: The Case of Dynamic Groups
Abstract

A first step toward establishing foundations for group signatures was taken
by Bellare,
Micciancio and Warinschi (Eurocrypt 2003)
with a treatment of the case where the
group is static. However the bulk of existing practical schemes and
applications are for dynamic groups, and these involve important new elements
and security issues. This paper treats this case, providing foundations for
dynamic group signatures, in the form of a model, strong formal definitions of
security, and a construction proven secure under general assumptions. We
believe this is an important and useful step because it helps bridge the gap
between Bellare
Micciancio and Warinschi
and the previous practical work, and
delivers a basis on which existing practical schemes may in future be
evaluated or proven secure.

2004

EPRINT

The Power of Verification Queries in Message Authentication and Authenticated Encryption
Abstract

This paper points out that, contrary to popular belief,
allowing a message authentication adversary multiple verification attempts
towards forgery is NOT equivalent to allowing it a single one, so that
the notion of security that most message authentication schemes are proven to
meet does not guarantee their security in practice. We then show, however, that
the equivalence does hold for STRONG unforgeability. Based on this we
recover security of popular classes of message authentication schemes such as
MACs (including HMAC and PRF-based MACs) and CW-schemes. Furthermore, in many
cases we do so with a TIGHT security reduction, so that in the end
the news we bring is surprisingly positive given the initial negative result.
Finally, we show analogous results for authenticated encryption.

2004

EPRINT

Code-Based Game-Playing Proofs and the Security of Triple Encryption
Abstract

The game-playing technique is a powerful tool for analyzing cryptographic
constructions. We illustrate this by using games as the central tool for
proving security of three-key triple-encryption, a long-standing open problem.
Our result, which is in the ideal-cipher model, demonstrates that for DES
parameters (56-bit keys and 64-bit plaintexts) an adversary's maximal advantage
is small until it asks about $2^{78}$ queries. Beyond this application, we
develop the foundations for game playing, formalizing a general framework for
game-playing proofs and discussing techniques used within such proofs. To
further exercise the game-playing framework we show how to use games to get
simple proofs for the PRP/PRF Switching Lemma, the security of the basic CBC
MAC, and the chosen-plaintext-attack security of OAEP.

2003

EUROCRYPT

2003

EPRINT

Hash Function Balance and its Impact on Birthday Attacks
Abstract

Textbooks tell us that a birthday attack on a hash function
$h$ with range size $r$ requires $r^{1/2}$ trials (hash computations) to find a
collision. But this is misleading, being true only if $h$ is regular, meaning
all points in the range have the same number of pre-images under $h$; if $h$ is
not regular, \textit{fewer} trials may be required. But how much fewer? This
paper addresses this question by introducing a measure of the ``amount of
regularity'' of a hash function that we call its balance, and then providing
estimates of the success-rate of the birthday attack as a function of the
balance of the hash function being attacked. In particular, we will see that
the number of trials to find a collision can be significantly less than
$r^{1/2}$ for hash functions of low balance. This leads us to examine popular
design principles, such as the MD (Merkle-Damg{\aa}rd) transform, from the
point of view of balance preservation, and to mount experiments to determine
the balance of popular hash functions.

2003

EPRINT

EAX: A Conventional Authenticated-Encryption Mode
Abstract

We propose a block-cipher mode of operation, called EAX, for
authenticated-encryption with associated-data (AEAD). Given a nonce N, a
message M, and a header H, the mode protects the privacy of M and the
authenticity of both M and H. Strings N,M,H$ are arbitrary, and the mode uses
$2\lceil |M|/n \rceil + \lceil |H|/n\rceil + \lceil |N|/n\rceil$ block-cipher
calls when these strings are nonempty and n is the block length of the
underlying block cipher. Among EAX's characteristics are that it is on-line
(the length of a message isn't needed to begin processing it) and a fixed
header can be pre-processed, effectively removing the per-message cost of
binding it to the ciphertext. EAX is obtained by instantiating a simple
generic-composition method, and then collapsing its two keys into one. EAX is
provably secure under a standard complexity-theoretic assumption.
EAX was designed in response to the expressed need of several
standardization bodies, including NIST, IETF and IEEE 802.11, for a patent-free
AEAD scheme. Such a scheme would have to be conventional, meaning it
would make two passes, one aimed at achieving privacy and one aimed at
achieving authenticity. EAX aims to fill this need by doing as well as
possible within the space of conventional schemes with regard to issues of
efficiency, simplicity, elegance, ease of correct use, and provable-security
guarantees. EAX is an alternative to CCM.

2003

EPRINT

An Uninstantiable Random-Oracle-Model Scheme for a Hybrid Encryption Problem
Abstract

We present a simple, natural random-oracle (RO) model
scheme, for a practical goal, that is uninstantiable,
meaning is proven in the RO model to meet its goal yet admits
NO standard-model instantiation that meets this goal. The
goal in question is IND-CCA-preserving asymmetric
encryption which formally captures security of the most common
practical usage of asymmetric encryption, namely to transport a
symmetric key in such a way that symmetric encryption under the
latter remains secure. The scheme is an ElGamal variant, called
Hash ElGamal, that resembles numerous existing RO-model schemes,
and on the surface shows no evidence of its anomalous properties.
More generally, we show that a certain goal, that we call
key-verifiable, ciphertext-verifiable IND-CCA-preserving
asymmetric encryption, is achievable in the RO model (by Hash
ElGamal in particular) but unachievable in the standard model.
This helps us better understand the source of the anomalies in
Hash ElGamal and also lifts our uninstantiability result from
being about a specific scheme to being about a primitive or goal.
These results extend our understanding of the gap between the
standard and RO models, and bring concerns raised by previous work
closer to practice by indicating that the problem of RO-model
schemes admitting no secure instantiation can arise in domains
where RO schemes are commonly designed.

2002

EUROCRYPT

2002

EPRINT

From Identification to Signatures via the Fiat-Shamir Transform: Minimizing Assumptions for Security and Forward-Security
Abstract

The Fiat-Shamir paradigm for transforming
identification schemes into signature schemes has been popular since
its introduction because it yields efficient signature schemes, and
has been receiving renewed interest of late as the main tool in
deriving forward-secure signature schemes.
We find minimal (meaning
necessary and sufficient) conditions on the identification scheme to
ensure security of the signature scheme in the random oracle model,
in both the usual and the forward-secure cases.
Specifically we show that the signature scheme is secure
(resp. forward-secure) against chosen-message attacks in the random
oracle model if and only if the underlying identification
scheme is secure (resp. forward-secure) against impersonation under
passive (i.e.. eavesdropping only) attacks, and has its
commitments drawn at random from a large space. An extension is
proven incorporating a random seed into the Fiat-Shamir transform so
that the commitment space assumption may be removed.

2002

EPRINT

Protecting against Key Exposure: Strongly Key-Insulated Encryption with Optimal Threshold
Abstract

A new framework for protection against key exposure was
recently suggested by Dodis et. al.. We take its realization
further towards practice by presenting simple new schemes that provide benefits
over previous ones in terms of scalability, performance and security. Our first
contribution is a simple, practical, scalable scheme called SKIE-OT that
achieves the best possible security in their framework. SKIE-OT is based on
the Boneh-Franklin identity-based encryption (IBE) scheme and
exploits algebraic properties of the latter. We also show that the role of
identity-based encryption is not coincidental by proving that IBE is equivalent
to (not strongly) key-insulated encryption with optimal threshold and allowing
random-access key updates.

2001

EPRINT

OCB Mode
Abstract

This paper was prepared for NIST, which is considering new
block-cipher modes of operation. It describes a parallelizable
mode of operation that simultaneously provides both privacy
and authenticity. "OCB mode" encrypts-and-authenticates
an arbitrary message $M\in\bits^*$ using only $\lceil |M|/n\rceil + 2$
block-cipher invocations, where $n$ is the block length of the
underlying block cipher. Additional overhead is small.
OCB refines a scheme, IAPM, suggested by Jutla [IACR-2000/39], who
was the first to devise an authenticated-encryption mode with minimal
overhead compared to standard modes. Desirable new properties of
OCB include: very cheap offset calculations; operating on an arbitrary
message $M\in\bits^*$; producing ciphertexts of minimal length;
using a single underlying cryptographic key; making a nearly optimal number
of block-cipher calls; avoiding the need for a random IV; and rendering it
infeasible for an adversary to find "pretag collisions". The paper
provides a full proof of security for OCB.

2001

EPRINT

Forward-Security in Private-Key Cryptography
Abstract

This paper provides a comprehensive treatment of
forward-security in the context of shared-key based cryptographic primitives,
as a practical means to mitigate the damage caused by key-exposure. We provide
definitions of security, practical proven-secure constructions, and
applications for the main primitives in this area. We identify forward-secure
pseudorandom bit generators as the central primitive, providing several
constructions and then showing how forward-secure message authentication
schemes and symmetric encryption schemes can be built based on standard schemes
for these problems coupled with forward-secure pseudorandom bit generators. We
then apply forward-secure message authentication schemes to the problem of
maintaining secure access logs in the presence of break-ins.

2001

EPRINT

The Security of Practical Two-Party RSA Signature Schemes
Abstract

In a two-party RSA signature scheme, a client and server, each
holding a share of an RSA decryption exponent $d$, collaborate to compute an
RSA signature under the corresponding public key $N,e$ known to both. This
primitive is of growing interest in the domain of server-aided password-based
security, where the client's share of $d$ is based on its password. To minimize
cost, designers are looking at very simple, practical protocols based on the
early ideas of Boyd, but their security is unclear. We analyze a class of these
protocols. We suggest two notions of security for two-party signature schemes
and provide proofs of security for the schemes in our class based on
assumptions about RSA and the hash function underlying the scheme.

2000

ASIACRYPT

2000

ASIACRYPT

2000

ASIACRYPT

2000

EPRINT

Identification Protocols Secure Against Reset Attacks
Abstract

We provide identification protocols that are secure even
when the adversary can reset the internal state and/or randomization source of
the user identifying itself, and when executed in an asynchronous environment
like the Internet that gives the adversary concurrent access to instances of
the user. These protocols are suitable for use by devices (like smartcards)
which when under adversary control may not be able to reliably maintain their
internal state between invocations.

2000

EPRINT

The Security of Chaffing and Winnowing
Abstract

This paper takes a closer look at Rivest's
chaffing-and-winnowing paradigm for data privacy. We begin with a
\textit{definition} which enables one to determine clearly whether a
given scheme qualifies as ``chaffing-and-winnowing.'' We then analyze
Rivest's schemes to see what quality of data privacy they provide. His
simplest scheme is easily proven secure but is ineffient. The security
of his more efficient scheme ---based on all-or-nothing transforms
(AONTs)--- is however more problematic. It can be attacked under
Rivest's definition of security of an AONT, and even under stronger
notions does not appear provable. We show however that by using a OAEP
as the AONT one can prove security. We also present a different scheme,
still using AONTs, that is equally efficient and easily proven secure
even under the original weak notion of security of AONTs.

2000

EPRINT

Authenticated Key Exchange Secure Against Dictionary Attacks
Abstract

This paper gives definitions and results about password-based
protocols for authenticated key exchange (AKE), mutual authentication
MA), and the combination of these goals (AKE, MA).
Such protocols are designed to work despite interference by an active
adversary and despite the use of passwords drawn from a space so small
that an adversary might well enumerate, off line,
a user's password.
While several such password-based protocols have been suggested,
the underlying theory has been lagging, and
some of the protocols don't actually work.
This is an area strongly in need of foundations,
but definitions and theorems here can get overwhelmingly complex.
To help manage this complexity we begin by defining a model, one rich enough
to deal with password guessing, forward secrecy,
server compromise, and loss of session keys.
The one model can be used to
define various goals.
We take AKE (with implicit authentication---no one besides
your intended partner could possibly get the key, though he may or may
not actually get it) as the basic goal.
Then we prove that any secure
AKE protocol can be
embellished (in a simple and generic way)
to also provide for MA.
This approach turns out to be simpler than trying to
augment an MA protocol to also distribute a session key.
Next we prove correctness for the idea at the center
of the Encrypted Key-Exchange (EKE) protocol
of Bellovin and Merritt:
we prove (in an ideal-cipher model) that
the two-flow protocol at the core of EKE is
a secure AKE.
Combining with the result above we have a
simple 3-flow protocol for AKE,MA which is
proven secure against dictionary attack.

2000

EPRINT

Authenticated Encryption: Relations among notions and analysis of the generic composition paradigm
Abstract

An authenticated encryption scheme is a symmetric encryption scheme whose goal is to provide both privacy and integrity. We consider two possible notions of authenticity for such schemes, namely integrity of plaintexts and integrity of ciphertexts, and relate them (when coupled with IND-CPA) to the standard notions of privacy (IND-CCA, NM-CPA) by presenting implications and separations between all notions considered. We then analyze the security of authenticated encryption schemes designed by ``generic composition,'' meaning making black-box use of a given symmetric encryption scheme and a given MAC. Three composition methods are considered, namely Encrypt-and-MAC, MAC-then-encrypt, and Encrypt-then-MAC. For each of these, and for each notion of security, we indicate whether or not the resulting scheme meets the notion in question assuming the given symmetric encryption scheme is secure against chosen-plaintext attack and the given MAC is unforgeable under chosen-message attack. We provide proofs for the cases where the answer is ``yes'' and counter-examples for the cases where the answer is ``no.''

1999

EPRINT

A forward-secure digital signature scheme
Abstract

We describe a digital signature scheme in which the
public key is fixed but the secret signing key is updated at regular
intervals so as to provide a <i>forward security</i> property:
compromise of the current secret key does not enable an adversary to
forge signatures pertaining to the past. This can be useful to
mitigate the damage caused by key exposure without requiring
distribution of keys. Our construction uses ideas from the
Fiat-Shamir and Ong-Schnorr identification and
signature schemes, and is proven to be forward secure based
on the hardness of factoring, in the random oracle model. The
construction is also quite efficient.

1999

EPRINT

DHAES: An Encryption Scheme Based on the Diffie-Hellman Problem
Abstract

scheme, DHAES. The scheme is as efficient as ElGamal encryption, but has
stronger security properties. Furthermore, these security properties are proven
to hold under appropriate assumptions on the underlying primitive.
We show that DHAES has not only the ``basic'' property of secure encryption
(namely privacy under a chosen-plaintext attack) but also achieves privacy
under both non-adaptive and adaptive chosen-ciphertext attacks. (And hence
it also achieves non-malleability.)
DHAES is built in a generic way from lower-level primitives: a symmetric
encryption scheme, a message authentication code, group operations in an
arbitrary group, and a cryptographic hash function. In particular, the
underlying group may be an elliptic-curve group or the multiplicative
group of integers modulo a prime number.
The proofs of security are based on appropriate assumptions about the
hardness of the Diffie-Hellman problem and the assumption that the
underlying symmetric primitives are secure. The assumptions are
all standard in the sense that no random oracles are involved.
We suggest that DHAES provides an attractive starting point for developing
public-key encryption standards based on the Diffie-Hellman assumption.

1999

EPRINT

Non-Malleable Encryption: Equivalence between Two Notions, and an Indistinguishability-Based Characterization
Abstract

We prove the equivalence of two definitions of non-malleable
encryption appearing in the literature--- the original one of Dolev, Dwork
and Naor and the later one of Bellare, Desai, Pointcheval and Rogaway. The
equivalence relies on a new characterization of non-malleable encryption in
terms of the standard notion of indistinguishability of Goldwasser and
Micali. We show that non-malleability is equivalent to indistinguishability
under a ``parallel chosen ciphertext attack,'' this being a new kind of
chosen ciphertext attack we introduce, in which the adversary's decryption
queries are not allowed to depend on answers to previous queries, but must be
made all at once. This characterization simplifies both the notion of
non-malleable encryption and its usage, and enables one to see more easily
how it compares with other notions of encryption. The results here apply to
non-malleable encryption under any form of attack, whether chosen-plaintext,
chosen-ciphertext, or adaptive chosen-ciphertext.

1999

EPRINT

A tool for obtaining tighter security analyses of pseudorandom function based constructions, with applications to PRP to PRF conversion
Abstract

We present a general probabilistic lemma that can be applied
to upper bound the advantage of an adversary in distinguishing between two
families of functions. Our lemma reduces the task of upper bounding the
advantage to that of upper bounding the ratio of two probabilities associated
to the adversary, when this ratio is is viewed as a random variable. It
enables us to obtain significantly tighter analyses than more conventional
methods.
In this paper we apply the technique to the problem of PRP to PRF conversion.
We present a simple, new construction of a PRF from a PRP that makes only
two invocations of the PRP and has insecurity linear in the number of
queries made by the adversary. We also improve the analysis of the
truncation construction.

1998

EPRINT

Fast Batch Verification for Modular Exponentiation and Digital Signatures
Abstract

Many tasks in cryptography (e.g., digital signature
verification) call for verification of a basic operation like modular
exponentiation in some group: given (g,x,y) check that g<sup>x</sup>=y.
This is typically done by re-computing g<sup>x</sup> and checking we get y.
We would like to do it differently, and faster.
The approach we use is batching. Focusing first on the basic modular
exponentiation operation, we provide some probabilistic batch verifiers, or
tests, that verify a sequence of modular exponentiations significantly faster
than the naive re-computation method. This yields speedups for several
verification tasks that involve modular exponentiations.
Focusing specifically on digital signatures, we then suggest a weaker notion of
(batch) verification which we call ``screening.'' It seems useful for many
usages of signatures, and has the advantage that it can be done very fast;
in particular, we show how to screen a sequence of RSA signatures at the
cost of one RSA verification plus hashing.

1998

EPRINT

A Modular Approach to the Design and Analysis of Authentication and Key Exchange Protocols
Abstract

We present a general framework for constructing and analyzing authentication
protocols in realistic models of communication networks. This framework
provides a sound formalization for the authentication problem and suggests
simple and attractive design principles for general authentication and key
exchange protocols. The key element in our approach is a modular treatment of
the authentication problem in cryptographic protocols; this applies to the
definition of security, to the design of the protocols, and to their analysis.
In particular, following this modular approach, we show how to systematically
transform solutions that work in a model of idealized authenticated
communications into solutions that are secure in the realistic setting of
communication channels controlled by an active adversary.
Using these principles we construct and prove the security of simple and
practical authentication and key-exchange protocols. In particular, we provide
a security analysis of some well-known key exchange protocols (e.g.
authenticated Diffie-Hellman key exchange), and of some of the techniques
underlying the design of several authentication protocols that are currently
being deployed on a large scale for the Internet Protocol and other
applications.

1998

EPRINT

Many-to-one Trapdoor Functions and their Relation to Public-key Cryptosystems
Abstract

The heart of the task of building public key cryptosystems is viewed
as that of ``making trapdoors;'' in fact, public key cryptosystems and
trapdoor functions are often discussed as synonymous. How accurate is
this view? In this paper we endeavor to get a better understanding of
the nature of ``trapdoorness'' and its relation to public key
cryptosystems, by broadening the scope of the investigation: we look
at general trapdoor functions; that is, functions that are not
necessarily injective (ie., one-to-one). Our first result is somewhat
surprising: we show that non-injective trapdoor functions (with
super-polynomial pre-image size) can be constructed {from} any one-way
function (and hence it is unlikely that they suffice for public key
encryption). On the other hand, we show that trapdoor functions with
polynomial pre-image size are sufficient for public key encryption.
Together, these two results indicate that the pre-image size is a
fundamental parameter of trapdoor functions. We then turn our
attention to the converse, asking what kinds of trapdoor functions can
be constructed from public key cryptosystems. We take a first step by
showing that in the random-oracle model one can construct injective
trapdoor functions from any public key cryptosystem.

1998

EPRINT

Relations among Notions of Security for Public-Key Encryption Schemes
Abstract

We compare the relative strengths of popular notions of security for
public key encryption schemes. We consider the goals of
indistinguishability and non-malleability, each under chosen plaintext
attack and two kinds of chosen ciphertext attack. For each of the
resulting pairs of definitions we prove either an implication (every
scheme meeting one notion must meet the other) or a separation (there
is a scheme meeting one notion but not the other, assuming the first
notion can be met at all). We similarly treat plaintext awareness, a
notion of security in the random oracle model. An additional
contribution of this paper is a new definition of non-malleability
which we believe is simpler than the previous one.

1998

EPRINT

Security amplification by composition: The case of doubly-iterated, ideal ciphers
Abstract

We investigate, in the Shannon model, the security of constructions
corresponding to double and (two-key) triple DES. That is, we
consider F<sub>k1</sub>(F<sub>k2</sub>(.)) and
F<sub>k1</sub>(F<sub>k2</sub><sup>-1</sup>(F<sub>k1</sub>(.))) with
the component functions being ideal ciphers. This models the
resistance of these constructions to ``generic'' attacks like meet
in the middle attacks.
We obtain the first proof that composition actually
increases the security in some meaningful sense. We compute a bound
on the probability of breaking the double cipher as a function of
the number of computations of the base cipher made, and the number
of examples of the composed cipher seen, and show that the success
probability is the square of that for a single key cipher. The
same bound holds for the two-key triple cipher. The first bound
is tight and shows that meet in the middle is the best possible
generic attack against the double cipher.

1997

EPRINT

A New Paradigm for Collision-free Hashing: Incrementality at Reduced Cost
Abstract

We present a simple, new paradigm for the design of collision-free hash
functions. Any function emanating from this paradigm is <i>incremental.</i>
(This means that if a message x which I have previously hashed is modified to
x' then rather than having to re-compute the hash of x' from scratch, I
can quickly ``update'' the old hash value to the new one, in time proportional
to the amount of modification made in x to get x'.) Also any function
emanating from this paradigm is parallelizable, useful for hardware
implementation.

1997

EPRINT

Round-Optimal Zero-Knowledge Arguments Based on any One-Way Function
Abstract

We fill a gap in the theory of zero-knowledge protocols by presenting
NP-arguments that achieve negligible error probability and computational
zero-knowledge in four rounds of interaction, assuming only the existence of a
one-way function. This result is optimal in the sense that four rounds and a
one-way function are each individually necessary to achieve a negligible error
zero-knowledge argument for NP.

1997

EPRINT

A note on negligible functions
Abstract

In theoretical cryptography, one formalizes the notion of an
adversary's success probability being ``too small to matter'' by asking that it
be a negligible function of the security parameter. We argue that the issue
that really arises is what it might mean for a collection of functions
to be ``negligible.'' We consider (and define) two such notions, and prove them
equivalent. Roughly, this enables us to say that any cryptographic primitive
has a specific associated ``security level.'' In particular we say this
for any one-way function. We also reconcile different definitions of negligible
error arguments and computational proofs of knowledge that have appeared in the
literature. Although the motivation is cryptographic, the main result is
purely about negligible functions.

1996

EPRINT

Verifiable Partial Key Escrow
Abstract

One of the main objections to existing proposals for key escrow is that the
individual's privacy relies on too high a level of trust in the law enforcement
agencies. In particular, even if the government is trustworthy today, it may be
replaced by an un-trustworthy government tomorrow which could immediately and
suddenly recover the secret keys of all users.

#### Program Committees

- PKC 2018
- Crypto 2017
- Crypto 2013
- Crypto 2011
- TCC 2007
- Asiacrypt 2006
- Crypto 2003
- Crypto 2000 (Program chair)
- Eurocrypt 1999
- Crypto 1996
- Eurocrypt 1995
- Crypto 1993

#### Coauthors

- Michel Abdalla (9)
- Tolga Acar (2)
- William Aiello (2)
- Jee Hea An (4)
- Benedikt Auerbach (1)
- Mira Belenkiy (2)
- Daniel J. Bernstein (1)
- John Black (1)
- Alexandra Boldyreva (12)
- Zvika Brakerski (1)
- Ran Canetti (2)
- David Cash (5)
- Dario Catalano (3)
- Lenore Cowen (1)
- Giovanni Di Crescenzo (2)
- Wei Dai (2)
- Hannah Davis (1)
- Anand Desai (3)
- Rafael Dowsley (3)
- Shanshan Duan (1)
- Marc Fischlin (4)
- Georg Fuchsbauer (2)
- Juan A. Garay (2)
- Oded Goldreich (5)
- Shafi Goldwasser (7)
- Roch Guérin (1)
- Felix Günther (1)
- Shai Halevi (2)
- Viet Tung Hoang (6)
- Dennis Hofheinz (2)
- Russell Impagliazzo (1)
- Joseph Jaeger (2)
- Markus Jakobsson (2)
- Daniel Kane (2)
- Sriram Keelveedhi (9)
- Joe Kilian (1)
- Eike Kiltz (6)
- Lars R. Knudsen (3)
- Tadayoshi Kohno (7)
- Hugo Krawczyk (3)
- Ted Krovetz (2)
- Tanja Lange (3)
- Lucy Li (1)
- John Malone-Lee (3)
- Sarah Meiklejohn (1)
- Silvio Micali (5)
- Daniele Micciancio (4)
- Rachel Miller (1)
- Sara K. Miner (2)
- Anton Mityagin (1)
- Chanathip Namprempre (12)
- Moni Naor (1)
- Gregory Neven (9)
- Ruth Ng (1)
- Maya Nyayapati (1)
- Adam O'Neill (4)
- Pascal Paillier (3)
- Adriana Palacio (9)
- Kenneth G. Paterson (3)
- Chris Peikert (1)
- Krzysztof Pietrzak (1)
- Bertram Poettering (2)
- David Pointcheval (6)
- Tal Rabin (2)
- Thomas Ristenpart (10)
- Todor Ristov (3)
- Ronald L. Rivest (1)
- Phillip Rogaway (25)
- Amit Sahai (5)
- Ravi Sandhu (1)
- Alessandra Scafuro (1)
- Gil Segev (1)
- Michael Semanko (1)
- Hovav Shacham (1)
- Haixia Shi (4)
- Sarah Shoup (2)
- Victor Shoup (1)
- Asha Camper Singh (1)
- Jessica Staddon (1)
- Douglas Stebila (2)
- Igors Stepanovs (8)
- Björn Tackmann (3)
- Stefano Tessaro (6)
- Susan Thomson (2)
- Salil P. Vadhan (2)
- Alexander Vardy (1)
- Ramarathnam Venkatesan (2)
- David Wagner (2)
- Bogdan Warinschi (1)
- Brent Waters (5)
- Bennet Yee (1)
- Scott Yilek (6)
- Moti Yung (4)
- Chong Zhang (1)