## CryptoDB

### David Cash

#### Publications

**Year**

**Venue**

**Title**

2022

PKC

Encapsulated Search Index : Public-Key, Sub-linear, Distributed, and Delegatable
📺
Abstract

We build the first *sub-linear* (in fact, potentially constant-time) *public-key* searchable encryption system:
- server can publish a public key $PK$.
- anybody can build an encrypted index for document $D$ under $PK$.
- client holding the index can obtain a
token $z_w$ from the server to check if a keyword $w$ belongs to $D$.
- search using $z_w$ is almost as fast (e.g., sub-linear) as the non-private search.
- server granting the token does not learn anything about the document $D$, beyond the keyword $w$.
- yet, the token $z_w$ is specific to the pair $(D,w)$: the client does not learn if other keywords $w'\neq w$ belong to $D$, or if $w$ belongs to other, freshly indexed documents $D'$.
- server cannot fool the client by giving a wrong token $z_w$.
We call such a primitive *encapsulated search index* (ESI). Our ESI scheme can be made $(t,n)$-distributed among $n$ servers in the best possible way: *non-interactive*, verifiable, and resilient to any coalition of up to $(t-1)$ malicious servers. We also introduce the notion of *delegatable* ESI and show how to extend our construction to this setting.
Our solution --- including public indexing, sub-linear search, delegation, and distributed token generation --- is deployed as a commercial application by a real-world company.

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.

2009

CRYPTO

#### Program Committees

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

#### Coauthors

- Tolga Acar (1)
- Akshima (1)
- Benny Applebaum (1)
- Erik Aronesty (1)
- Benedikt Auerbach (1)
- Mira Belenkiy (1)
- Mihir Bellare (3)
- Alexandra Boldyreva (1)
- Zvika Brakerski (1)
- Yan Zong Ding (1)
- Yevgeniy Dodis (2)
- Rafael Dowsley (1)
- Andrew Drucker (2)
- Manuel Fersch (1)
- Marc Fischlin (1)
- Daniel H. Gallancy (1)
- Matthew Green (1)
- Christopher Higley (1)
- Dennis Hofheinz (2)
- Susan Hohenberger (1)
- Alexander Hoover (1)
- Abhishek Jain (2)
- Stanislaw Jarecki (1)
- Charanjit S. Jutla (1)
- Harish Karthikeyan (1)
- Eike Kiltz (9)
- Hugo Krawczyk (1)
- Alptekin Küpçü (2)
- Wenke Lee (1)
- Richard J. Lipton (1)
- 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 (2)
- Michael Steiner (1)
- Stefano Tessaro (2)
- Rotem Tsabary (1)
- Oren Tysor (1)
- Daniele Venturi (2)
- Shabsi Walfish (1)
- Bogdan Warinschi (1)
- Hoeteck Wee (2)
- Daniel Wichs (2)
- Mark Zhandry (1)
- Cong Zhang (2)