## CryptoDB

### David Cash

#### Affiliation: University of Chicago

#### Publications

**Year**

**Venue**

**Title**

2020

CRYPTO

Time-Space Tradeoffs and Short Collisions in Merkle-Damgård Hash Functions
📺
Abstract

We study collision-finding against Merkle-Damgård hashing in the random-oracle model by adversaries with an arbitrary $S$-bit auxiliary advice input about the random oracle and $T$ queries. Recent work showed that such adversaries can find collisions (with respect to a random IV) with advantage $\Omega(ST^2/2^n)$, where $n$ is the output length, beating the birthday bound by a factor of $S$. These attacks were shown to be optimal.
We observe that the collisions produced are very long, on the order $T$ blocks, which would limit their practical relevance. We prove several results related to improving these attacks to find short collisions. We first exhibit a simple attack for finding $B$-block-long collisions achieving advantage $\tilde{\Omega}(STB/2^n)$. We then study if this attack is optimal. We show that the prior technique based on the bit-fixing model (used for the $ST^2/2^n$ bound) provably cannot reach this bound, and towards a general result we prove there are qualitative jumps in the optimal attacks for finding length $1$, length $2$, and unbounded-length collisions. Namely, the optimal attacks achieve (up to logarithmic factors) order of $(S+T)/2^n$, $ST/2^n$ and $ST^2/2^n$ advantage. We also give an upper bound on the advantage of a restricted class of short-collision finding attacks via a new analysis on the growth of trees in random functional graphs that may be of independent interest.

2020

TCC

A Lower Bound for One-Round Oblivious RAM
📺
Abstract

We initiate a fine-grained study of the round complexity of Oblivious RAM
(ORAM). We prove that any one-round balls-in-bins ORAM that does not
duplicate balls must have either $\Omega(\sqrt{N})$ bandwidth or
$\Omega(\sqrt{N})$ client memory, where $N$ is the number of memory slots
being simulated. This shows that such schemes are strictly weaker than
general (multi-round) ORAMs or those with server computation, and in
particular implies that a one-round version of the original square-root
ORAM of Goldreich and Ostrovksy (J. ACM 1996) is optimal. We prove this
bound via new techniques that differ from those of Goldreich and Ostrovksy,
and of Larsen and Nielsen (CRYPTO 2018), which achieved an $\Omega(\log N)$
bound for balls-in-bins and general multi-round ORAMs respectively.
Finally we give a weaker extension of our bound that allows for limited
duplication of balls, and also show that our bound extends to
multiple-round ORAMs of a restricted form that include the best known
constructions.

2018

TCC

A Ciphertext-Size Lower Bound for Order-Preserving Encryption with Limited Leakage
Abstract

We consider a security definition of Chenette, Lewi, Weis, and Wu for order-revealing encryption (ORE) and order-preserving encryption (OPE) (FSE 2016). Their definition says that the comparison of two ciphertexts should only leak the index of the most significant bit on which they differ. While their work could achieve order-revealing encryption with short ciphertexts that expand the plaintext by a factor $$\approx 1.58$$, it could only find order-preserving encryption with longer ciphertexts that expanded the plaintext by a security-parameter factor. We give evidence that this gap between ORE and OPE is inherent, by proving that any OPE meeting the information-theoretic version of their security definition (for instance, in the random oracle model) must have ciphertext length close to that of their constructions. We extend our result to identify an abstract security property of any OPE that will result in the same lower bound.

2018

ASIACRYPT

Parameter-Hiding Order Revealing Encryption
Abstract

Order-revealing encryption (ORE) is a primitive for outsourcing encrypted databases which allows for efficiently performing range queries over encrypted data. Unfortunately, a series of works, starting with Naveed et al. (CCS 2015), have shown that when the adversary has a good estimate of the distribution of the data, ORE provides little protection. In this work, we consider the case that the database entries are drawn identically and independently from a distribution of known shape, but for which the mean and variance are not (and thus the attacks of Naveed et al. do not apply). We define a new notion of security for ORE, called parameter-hiding ORE, which maintains the secrecy of these parameters. We give a construction of ORE satisfying our new definition from bilinear maps.

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.

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

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

EPRINT

Foundations of Non-Malleable Hash and One-Way Functions
Abstract

Non-malleability is an interesting and useful property which ensures
that a cryptographic protocol preserves the independence of the
underlying values: given for example an encryption Enc(m) of some
unknown message m, it should be hard to transform this ciphertext
into some encryption Enc(m*) of a related message m*. This
notion has been studied extensively for primitives like encryption,
commitments and zero-knowledge.
Non-malleability of one-way functions and hash functions has
surfaced as a crucial property in several recent results,
but it has not undergone a comprehensive
treatment so far. In this paper we initiate the study of such
non-malleable functions. We start with the design of an appropriate
security definition. We then show that non-malleability for hash and
one-way functions can be achieved, via a theoretical
construction that uses perfectly one-way hash functions and
simulation-sound non-interactive zero-knowledge proofs of knowledge
(NIZKPoK).
We also discuss the complexity of non-malleable hash
and one-way functions. Specifically, we give a black-box based separation of non-malleable functions from one-way permutations (which our construction bypasses due to the 'non-black-box' NIZKPoK).
We exemplify the usefulness of our definition in
cryptographic applications by showing that non-malleability is
necessary and sufficient to securely replace one of the two random
oracles in the IND-CCA encryption scheme by Bellare and Rogaway, and
to improve the security of client-server puzzles.

2009

CRYPTO

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.

2005

EPRINT

Intrusion-Resilient Authentication in the Limited Communication Model
Abstract

We describe a general technique for building authentication systems
that resist compromises at the client side. We derive this resistance
by storing key information on hardware fast enough for valid use
but too slow for an intruder (e.g., a virus) to capture much of the key before being detected and removed. We give formal models for two types of protocols: user authentication and authenticated session-key
generation. The first can be used for physical authentication tokens, e.g., used for gaining access to a building. The second can be used for conducting secure remote sessions on laptops that are occasionally
infected by viruses. We present and analyze protocols for each of these tasks and describe how they can be implemented. With one example setting of parameters, in the case of user authentication, we are able to guarantee security for 6 months using a device storing 384MB, and in the key generation protocol, a 128GB drive guarantees that an adversary would need 700 days to compromise the key information.
The model for intrusion resilience considered in this paper was
first introduced by Dagon et al. \cite{DLL05} and motivated by
the bounded storage model for cryptography \cite{Mau92}. Recently Dziembowski \cite{Dzi05} independently developed this model, and studied the same problems as the ones addressed in this paper. Our user authentication protocol is essentially the same as that of \cite{Dzi05}, while our authenticated session-key generation protocol builds on that of \cite{Dzi05}.

#### Program Committees

- Crypto 2020
- Eurocrypt 2019
- Eurocrypt 2016
- Eurocrypt 2014
- PKC 2014
- Crypto 2013
- PKC 2013
- Eurocrypt 2012
- Asiacrypt 2012

#### Coauthors

- Tolga Acar (2)
- Akshima (1)
- Benny Applebaum (1)
- Benedikt Auerbach (1)
- Mira Belenkiy (2)
- Mihir Bellare (5)
- Alexandra Boldyreva (2)
- Zvika Brakerski (1)
- Yan Zong Ding (2)
- Yevgeniy Dodis (1)
- Rafael Dowsley (1)
- Andrew Drucker (2)
- Manuel Fersch (1)
- Marc Fischlin (2)
- Matthew Green (1)
- Dennis Hofheinz (2)
- Susan Hohenberger (1)
- Alexander Hoover (1)
- Abhishek Jain (2)
- Stanislaw Jarecki (1)
- Charanjit S. Jutla (1)
- Eike Kiltz (10)
- Hugo Krawczyk (1)
- Alptekin Küpçü (2)
- Wenke Lee (2)
- Richard J. Lipton (2)
- Feng-Hao Liu (1)
- Rachel Miller (1)
- Adam O’Neill (1)
- Chris Peikert (3)
- Krzysztof Pietrzak (2)
- Marcel-Catalin Rosu (1)
- Amit Sahai (1)
- Victor Shoup (3)
- Michael Steiner (1)
- Stefano Tessaro (3)
- Rotem Tsabary (1)
- Daniele Venturi (2)
- Shabsi Walfish (1)
- Bogdan Warinschi (2)
- Hoeteck Wee (2)
- Daniel Wichs (2)
- Mark Zhandry (1)
- Cong Zhang (2)