## CryptoDB

### Phillip Rogaway

#### Affiliation: University of California, Davis

#### Publications

**Year**

**Venue**

**Title**

2019

ASIACRYPT

Anonymous AE
Abstract

The customary formulation of authenticated encryption (AE) requires the decrypting party to supply the correct nonce with each ciphertext it decrypts. To enable this, the nonce is often sent in the clear alongside the ciphertext. But doing this can forfeit anonymity and degrade usability. Anonymity can also be lost by transmitting associated data (AD) or a session-ID (used to identify the operative key). To address these issues, we introduce anonymous AE, wherein ciphertexts must conceal their origin even when they are understood to encompass everything needed to decrypt (apart from the receiver’s secret state). We formalize a type of anonymous AE we call anAE, anonymous nonce-based AE, which generalizes and strengthens conventional nonce-based AE, nAE. We provide an efficient construction for anAE, NonceWrap, from an nAE scheme and a blockcipher. We prove NonceWrap secure. While anAE does not address privacy loss through traffic-flow analysis, it does ensure that ciphertexts, now more expansively construed, do not by themselves compromise privacy.

2018

CRYPTO

Simplifying Game-Based Definitions
📺
Abstract

Often the simplest way of specifying game-based cryptographic definitions is apparently barred because the adversary would have some trivial win. Disallowing or invalidating these wins can lead to complex or unconvincing definitions. We suggest a generic way around this difficulty. We call it indistinguishability up to correctness, or IND$$\vert $$C. Given games $${{\text {G}}}$$ and $${{\text {H}}}$$ and a correctness condition $${{\text {C}}}$$ we define an advantage measure $${\mathbf {Adv}_{{{\text {G}}},{{\text {H}}},{{\text {C}}}}^{{\text {indc}}}}$$ wherein $${{{\text {G}}}}$$/$${{{\text {H}}}}$$ distinguishing attacks are effaced to the extent that they are inevitable due to $${{\text {C}}}$$. We formalize this in the language of oracle silencing, an alternative to exclusion-style and penalty-style definitions. We apply our ideas to a domain where game-based definitions have been cumbersome: stateful authenticated-encryption (sAE). We rework existing sAE notions and encompass new ones, like replay-free AE permitting a specified degree of out-of-order message delivery.

2012

ASIACRYPT

2010

EPRINT

On generalized Feistel networks
Abstract

We prove beyond-birthday-bound security for the well-known types of
generalized Feistel networks, including: (1) unbalanced Feistel networks, where the $n$-bit to $m$-bit round functions may have $n\ne m$; (2) alternating Feistel networks, where the round functions alternate between contracting and expanding; (3) type-1, type-2, and type-3 Feistel networks, where $n$-bit to $n$-bit round functions are used to encipher $kn$-bit strings for some $k\ge2$; and (4) numeric variants of any of the above, where one enciphers numbers in some given range rather than strings of some given size. Using a unified analytic framework we show that, in any of these settings, for
any $\varepsilon>0$, with enough rounds, the subject scheme can tolerate CCA attacks of up to $q\sim N^{1-\varepsilon}$ adversarial queries, where $N$ is the size of the round functions' domain (the size of the larger domain for alternating Feistel). This is asymptotically optimal. Prior analyses for generalized Feistel networks established security to only $q\sim N^{0.5}$ adversarial queries.

2007

EPRINT

How to Enrich the Message Space of a Cipher
Abstract

Given (deterministic) ciphers $\calE$ and~$E$ that can encipher messages of $\el$ and $n$ bits, respectively, we construct a cipher~$\calE^*=XLS[\calE,E]$ that can encipher messages of $\el+s$ bits for any $s<n$. Enciphering such a string will take one call to~$\calE$ and two calls to~$E$. We prove that~$\calE^*$ is a strong pseudorandom permutation as long as~$\calE$ and~$E$ are. Our construction works even in the tweakable and VIL (variable-input-length) settings. It makes use of a multipermutation (a pair of orthogonal Latin squares), a combinatorial object not previously used to get a provable-security result.

2006

EPRINT

Deterministic Authenticated-Encryption: A Provable-Security Treatment of the Key-Wrap Problem
Abstract

Standards bodies have been addressing the key-wrap problem, a
cryptographic goal that has never received a provable-security
treatment. In response, we provide one, giving definitions,
constructions, and proofs. We suggest that key-wrapâs goal is
security in the sense of deterministic authenticated-encryption
(DAE), a notion that we put forward. We also provide an alternative
notion, a pseudorandom injection (PRI), which we prove to be
equivalent. We provide a DAE construction, SIV, analyze its concrete
security, develop a blockcipher-based instantiation of it, and
suggest that the method makes a desirable alternative to the
schemes of the X9.102 draft standard. The construction incorporates
a method to turn a PRF that operates on a string into an equally
efficient PRF that operates on a vector of strings, a problem of
independent interest. Finally, we consider IV-based authenticated-
encryption (AE) schemes that are maximally forgiving of repeated
IVs, a goal we formalize as misuse-resistant AE.We show that a DAE
scheme with a vector-valued header, such as SIV, directly realizes
this goal.

2006

EPRINT

Formalizing Human Ignorance: Collision-Resistant Hashing without the Keys
Abstract

There is a rarely mentioned foundational problem involving collision-resistant hash-functions: common constructions are keyless, but formal definitions are keyed. The discrepancy stems from the fact that a function H:{0,1}^* -> {0,1}^n always admits an efficient collision-finding algorithm, it's just that us human beings might be unable to write the program down. We explain a simple way to sidestep this difficulty that avoids having to key our hash functions. The idea is to state theorems in a way that prescribes an explicitly-given reduction, normally a black-box one. We illustrate this approach using well-known examples involving digital signatures, pseudorandom functions, and the Merkle-Damgard construction.

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.

2004

ASIACRYPT

2004

EPRINT

Cryptographic Hash-Function Basics: Definitions, Implications and Separations for Preimage Resistance, Second-Preimage Resistance, and Collision Resistance
Abstract

We consider basic notions of security for cryptographic hash
functions: collision resistance, preimage resistance, and
second-preimage resistance. We give seven different definitions
that correspond to these three underlying ideas, and then we work out
all of the implications and separations among these seven definitions
within the concrete-security, provable-security framework. Because
our results are concrete, we can show two types of implications,
"conventional" and "provisional", where the strength of the latter depends on the amount of compression achieved by the hash function. We also distinguish two types of separations, "conditional" and "unconditional". When constructing counterexamples for our separations, we are careful to preserve specified hash-function domains and ranges; this rules out some pathological counterexamples and makes the separations more meaningful in practice.
Four of our definitions are standard while three appear to be new;
some of our relations and separations have appeared, others have not. Here we give a modern treatment that acts to catalog, in one place and with carefully-considered nomenclature, the most basic security notions for cryptographic hash functions.

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

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

A Critique of CCM
Abstract

CCM is a conventional authenticated-encryption scheme obtained from a
128-bit block cipher. The mechanism has been adopted as the mandatory
encryption algorithm in an IEEE 802.11 draft standard [15], and its use
has been proposed more broadly [16,17]. In this note we point out a
number of limitations of CCM. A related note provides an alternative
to CCM [5].

2003

EPRINT

A Parallelizable Enciphering Mode
Abstract

We describe a block-cipher mode of operation, EME, that turns an
n-bit block cipher into a tweakable enciphering scheme that acts
on strings of mn bits, where m \in [1..n]. The mode is parallelizable, but as serial-efficient as the non-parallelizable mode CMC. EME can be used to solve the disk-sector encryption problem. The algorithm entails two layers of ECB encryption and a "lightweight mixing" in between. We prove EME secure, in the reduction-based sense of modern cryptography. We motivate some of the design choices in EME by showing that a few
simple modifications of this mode are insecure.

2003

EPRINT

A Tweakable Enciphering Mode
Abstract

We describe a block-cipher mode of operation, CMC, that turns an n-bit block cipher into a tweakable enciphering scheme that acts on strings of mn bits, where m>=2. When the underlying block cipher is secure in the sense of a strong pseudorandom permutation (PRP), our scheme is secure in the sense of tweakable, strong PRP. Such an object can be used to encipher the sectors of a disk, in-place, offering security as good as can be obtained in this setting. CMC makes a pass of CBC encryption, xors in a mask, and then makes a pass of CBC decryption; no universal hashing, nor any other non-trivial operation beyond the block-cipher calls, is employed.
Besides proving the security of CMC we initiate a more general investigation of tweakable enciphering schemes, considering issues like the non-malleability of these objects.

2002

EPRINT

Encryption-Scheme Security in the Presence of Key-Dependent Messages
Abstract

Encryption that is only semantically secure should not be used on messages that depend on the underlying secret key; all bets are off when, for example,one encrypts using a shared key K the value K.
Here we introduce a new notion of security, KDM security, appropriate for key-dependent messages. The notion makes sense in both the public-key and shared-key settings. For the latter we show that KDM security is easily achievable within the random-oracle model.
By developing and achieving stronger notions of encryption-scheme security it is hoped that protocols which are proven secure under ``formal'' models of security can, in time, be safely realized by generically instantiating their primitives.

2002

EPRINT

Black-Box Analysis of the Block-Cipher-Based Hash-Function Constructions from PGV
Abstract

Preneel, Govaerts, and Vandewalle
considered the 64 most basic ways
to construct a hash function
$H:\{0,1\}^*\rightarrow\{0,1\}^n$ from a block cipher
$E:\{0,1\}^n\times\{0,1\}^n\rightarrow\{0,1\}^n$.
They regarded 12 of these 64 schemes as secure,
though no proofs or formal claims were given.
The remaining 52 schemes were shown to be subject to
various attacks.
Here we provide a formal and quantitative treatment of
the 64 constructions considered by PGV.
We prove that, in a black-box model, the 12
schemes that PGV singled out as secure really \textit{are} secure: we
give tight upper and lower bounds
on their collision resistance.
Furthermore, by stepping outside of
the Merkle-Damgard approach to analysis,
we show that an additional 8 of the 64 schemes
are just as collision resistant (up to a small constant) as the first group
of schemes.
Nonetheless, we are able to differentiate among the 20
collision-resistant
schemes by bounding their security as one-way functions.
We suggest that proving black-box bounds,
of the style given here, is a feasible and useful step
for understanding the security of any
block-cipher-based hash-function construction.

2002

EPRINT

The EMD Mode of Operation (A Tweaked, Wide-Blocksize, Strong PRP)
Abstract

We describe a block-cipher mode of operation, EMD,
that builds a strong pseudorandom permutation (PRP)
on $nm$ bits ($m\ge2$) out of
a strong PRP on $n$ bits (i.e., a block cipher).
The constructed PRP is also tweaked
(in the sense of [LRW02]):
to determine the $nm$-bit ciphertext block $C=\E_K^T(P)$
one provides, besides the key $K$ and the $nm$-bit plaintext block $P$, an $n$-bit tweak $T$.
The mode uses $2m$ block-cipher calls and
no other complex or computationally expensive steps
(such as universal hashing).
Encryption and decryption are identical except that encryption uses the
forward direction of the underlying block cipher and decryption uses the backwards
direction.
We suggest that EMD provides an attractive solution to the
disk-sector encryption problem, where one wants to encipher
the contents of an $nm$-bit disk sector in a way that
depends on the sector index and is secure against
chosen-plaintext/chosen-ciphertext attack.

2001

EPRINT

Ciphers with Arbitrary Finite Domains
Abstract

We introduce the problem of enciphering members of a finite set $M$
where $k=|M|$ is arbitrary (in particular, it need not be a power
of two). We want to achieve this goal starting from a block cipher
(which requires a message space of size $N=2^n$, for some $n$).
We look at a few solutions to this problem, focusing on the case
when $M=[0, k-1]$.

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

A Block-Cipher Mode of Operation for Parallelizable Message Authentication
Abstract

We define and analyze a
simple and fully parallelizable block-cipher mode of operation
for message authentication.
Parallelizability does not come at the
expense of serial efficiency: in a conventional, serial
environment, the algorithm's speed is within
a few percent of the (inherently sequential) CBC~MAC.
The new mode, PMAC, is deterministic,
resembles a standard mode of operation
(and not a Carter-Wegman MAC),
works for strings of any bit length,
employs a single block-cipher key,
and uses just max{1, ceiling(|M|/n)}
block-cipher calls to MAC any string M using an
n-bit block cipher.
We prove PMAC secure,
quantifying an adversary's forgery probability
in terms of the quality of the block cipher as a
pseudorandom permutation.

2000

ASIACRYPT

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.

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.

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.

#### Program Committees

- TCC 2015
- Eurocrypt 2013
- Crypto 2011
- Eurocrypt 2010
- Asiacrypt 2009
- Asiacrypt 2008
- Asiacrypt 2006
- FSE 2006
- Eurocrypt 2004
- PKC 2002
- Asiacrypt 2000
- Crypto 2000
- Crypto 1999
- Crypto 1998

#### Coauthors

- Martín Abadi (2)
- Michel Abdalla (1)
- Christian Badertscher (2)
- Donald Beaver (2)
- Mihir Bellare (25)
- Michael Ben-Or (1)
- John Black (11)
- John Chan (1)
- Don Coppersmith (2)
- Anand Desai (2)
- Joan Feigenbaum (2)
- Oded Goldreich (1)
- Shafi Goldwasser (1)
- Roch Guérin (1)
- Shai Halevi (4)
- Johan Håstad (1)
- Viet Tung Hoang (7)
- Daniel Kane (1)
- Joe Kilian (6)
- Hugo Krawczyk (1)
- Ted Krovetz (5)
- Christian Matt (2)
- Ueli Maurer (2)
- Silvio Micali (2)
- Ben Morris (4)
- Chanathip Namprempre (2)
- Kenneth G. Paterson (2)
- Krzysztof Pietrzak (1)
- David Pointcheval (4)
- Reza Reyhanitabar (2)
- Thomas Ristenpart (2)
- Thomas Shrimpton (10)
- Martijn Stam (1)
- Till Stegers (2)
- John P. Steinberger (2)
- Björn Tackmann (2)
- Damian Vizár (2)
- David Wagner (3)
- Mark Wooding (1)
- Yusi Zhang (1)
- Haibin Zhang (1)