## CryptoDB

### Justin Holmgren

#### Publications

**Year**

**Venue**

**Title**

2021

CRYPTO

Time- and Space-Efficient Arguments from Groups of Unknown Order
📺
Abstract

We construct public-coin time- and space-efficient zero-knowledge arguments for NP. For every time T and space S non-deterministic RAM computation, the prover runs in time T * polylog(T) and space S * polylog(T), and the verifier runs in time n * polylog(T), where n is the input length. Our protocol relies on hidden order groups, which can be instantiated with a trusted setup from the hardness of factoring (products of safe primes), or without a trusted setup using class groups. The argument-system can heuristically be made non-interactive using the Fiat-Shamir transform.
Our proof builds on DARK (Bunz et al., Eurocrypt 2020), a recent succinct and efficiently verifiable polynomial commitment scheme. We show how to implement a variant of DARK in a time- and space-efficient way. Along the way we:
1. Identify a significant gap in the proof of security of Dark.
2. Give a non-trivial modification of the DARK scheme that overcomes the aforementioned gap. The modified version also relies on significantly weaker cryptographic assumptions than those in the original DARK scheme. Our proof utilizes ideas from the theory of integer lattices in a novel way.
3. Generalize Pietrzak's (ITCS 2019) proof of exponentiation (PoE) protocol to work with general groups of unknown order (without relying on any cryptographic assumption).
In proving these results, we develop general-purpose techniques for working with (hidden order) groups, which may be of independent interest.

2020

TCC

Transparent Error Correcting in a Computationally Bounded World
📺
Abstract

We construct uniquely decodable codes against channels which are computationally bounded. Our construction requires only a public-coin (transparent) setup. All prior work for such channels either required a setup with secret keys and states, could not achieve unique decoding, or got worse rates (for a given bound on codeword corruptions). On the other hand, our construction relies on a strong cryptographic hash function with security properties that we only instantiate in the random oracle model.

2020

TCC

Public-Coin Zero-Knowledge Arguments with (almost) Minimal Time and Space Overheads
📺
Abstract

Zero-knowledge protocols enable the truth of a mathematical statement to be certified by a verifier without revealing any other information. Such protocols are a cornerstone of modern cryptography and recently are becoming more and more practical. However, a major bottleneck in deployment is the efficiency of the prover and, in particular, the space-efficiency of the protocol.
For every $\mathsf{NP}$ relation that can be verified in time $T$ and space $S$, we construct a public-coin zero-knowledge argument in which the prover runs in time $T \cdot \mathrm{polylog}(T)$ and space $S \cdot \mathrm{polylog}(T)$. Our proofs have length $\mathrm{polylog}(T)$ and the verifier runs in time $T \cdot \mathrm{polylog}(T)$ (and space $\mathrm{polylog}(T)$). Our scheme is in the random oracle model and relies on the hardness of discrete log in prime-order groups.
Our main technical contribution is a new space efficient \emph{polynomial commitment scheme} for multi-linear polynomials. Recall that in such a scheme, a sender commits to a given multi-linear polynomial $P:\mathbb{F}^n \to \mathbb{F}$ so that later on it can prove to a receiver statements of the form ``$P(x)=y$''. In our scheme, which builds on commitments schemes of Bootle et al. (Eurocrypt 2016) and B{\"u}nz et al. (S\&P 2018), we assume that the sender is given multi-pass streaming access to the evaluations of $P$ on the Boolean hypercube and we show how to implement both the sender and receiver in roughly time $2^n$ and space $n$ and with communication complexity roughly $n$.

2019

CRYPTO

On the Plausibility of Fully Homomorphic Encryption for RAMs
📺
Abstract

We initiate the study of fully homomorphic encryption for RAMs (RAM-FHE). This is a public-key encryption scheme where, given an encryption of a large database D, anybody can efficiently compute an encryption of P(D) for an arbitrary RAM program P. The running time over the encrypted data should be as close as possible to the worst case running time of P, which may be sub-linear in the data size.A central difficulty in constructing a RAM-FHE scheme is hiding the sequence of memory addresses accessed by P. This is particularly problematic because an adversary may homomorphically evaluate many programs over the same ciphertext, therefore effectively “rewinding” any mechanism for making memory accesses oblivious.We identify a necessary prerequisite towards constructing RAM-FHE that we call rewindable oblivious RAM (rewindable ORAM), which provides security even in this strong adversarial setting. We show how to construct rewindable ORAM using symmetric-key doubly efficient PIR (SK-DEPIR) (Canetti-Holmgren-Richelson, Boyle-Ishai-Pass-Wootters: TCC ’17). We then show how to use rewindable ORAM, along with virtual black-box (VBB) obfuscation for specific circuits, to construct RAM-FHE. The latter primitive can be heuristically instantiated using existing indistinguishability obfuscation candidates. Overall, we obtain a RAM-FHE scheme where the multiplicative overhead in running time is polylogarithmic in the database size N. Our basic scheme is single-hop, but we also extend it to obtain multi-hop RAM-FHE with overhead
$$N^\epsilon $$
for arbitrarily small
$$\epsilon >0$$
.We view our work as the first evidence that RAM-FHE is likely to exist.

2019

TCC

Permuted Puzzles and Cryptographic Hardness
Abstract

A permuted puzzle problem is defined by a pair of distributions
$$\mathcal{D}_0,\mathcal{D}_1$$
over
$$\varSigma ^n$$
. The problem is to distinguish samples from
$$\mathcal{D}_0,\mathcal{D}_1$$
, where the symbols of each sample are permuted by a single secret permutation
$$\pi $$
of [n].The conjectured hardness of specific instances of permuted puzzle problems was recently used to obtain the first candidate constructions of Doubly Efficient Private Information Retrieval (DE-PIR) (Boyle et al. & Canetti et al., TCC’17). Roughly, in these works the distributions
$$\mathcal{D}_0,\mathcal{D}_1$$
over
$${\mathbb F}^n$$
are evaluations of either a moderately low-degree polynomial or a random function. This new conjecture seems to be quite powerful, and is the foundation for the first DE-PIR candidates, almost two decades after the question was first posed by Beimel et al. (CRYPTO’00). However, while permuted puzzles are a natural and general class of problems, their hardness is still poorly understood.We initiate a formal investigation of the cryptographic hardness of permuted puzzle problems. Our contributions lie in three main directions:
Rigorous formalization. We formalize a notion of permuted puzzle distinguishing problems, extending and generalizing the proposed permuted puzzle framework of Boyle et al. (TCC’17).Identifying hard permuted puzzles. We identify natural examples in which a one-time permutation provably creates cryptographic hardness, based on “standard” assumptions. In these examples, the original distributions
$$\mathcal{D}_0,\mathcal{D}_1$$
are easily distinguishable, but the permuted puzzle distinguishing problem is computationally hard. We provide such constructions in the random oracle model, and in the plain model under the Decisional Diffie-Hellman (DDH) assumption. We additionally observe that the Learning Parity with Noise (LPN) assumption itself can be cast as a permuted puzzle.Partial lower bound for the DE-PIR problem. We make progress towards better understanding the permuted puzzles underlying the DE-PIR constructions, by showing that a toy version of the problem, introduced by Boyle et al. (TCC’17), withstands a rich class of attacks, namely those that distinguish solely via statistical queries.

2019

TCC

On the (In)security of Kilian-Based SNARGs
Abstract

The Fiat-Shamir transform is an incredibly powerful technique that uses a suitable hash function to reduce the interaction of general public-coin protocols. Unfortunately, there are known counterexamples showing that this methodology may not be sound (no matter what concrete hash function is used). Still, these counterexamples are somewhat unsatisfying, as the underlying protocols were specifically tailored to make Fiat-Shamir fail. This raises the question of whether this transform is sound when applied to natural protocols.One of the most important protocols for which we would like to reduce interaction is Kilian’s four-message argument system for all of
$$\mathsf {NP}$$
, based on collision resistant hash functions (
$$\mathsf {CRHF}$$
) and probabilistically checkable proofs (
$$\mathsf {PCP}$$
s). Indeed, an application of the Fiat-Shamir transform to Kilian’s protocol is at the heart of both theoretical results (e.g., Micali’s CS proofs) as well as leading practical approaches of highly efficient non-interactive proof-systems (e.g.,
$$\mathsf {SNARK}$$
s and
$$\mathsf {STARK}$$
s).In this work, we show significant obstacles to establishing soundness of (what we refer to as) the “Fiat-Shamir-Kilian-Micali” (
$$\mathsf {FSKM}$$
) protocol. More specifically:We construct a (contrived)
$$\mathsf {CRHF}$$
for which
$$\mathsf {FSKM}$$
is unsound for a very large class of
$$\mathsf {PCP}$$
s and for any Fiat-Shamir hash function. The collision-resistance of our
$$\mathsf {CRHF}$$
relies on very strong but plausible cryptographic assumptions. The statement is “tight” in the following sense: any
$$\mathsf {PCP}$$
outside the scope of our result trivially implies a
$$\mathsf {SNARK}$$
, eliminating the need for
$$\mathsf {FSKM}$$
in the first place.Second, we consider a known extension of Kilian’s protocol to an interactive variant of
$$\mathsf {PCP}$$
s called probabilistically checkable interactive proofs (
$$\mathsf {PCIP})$$
(also known as interactive oracle proofs or
$$\mathsf {IOP}$$
s). We construct a particular (contrived)
$$\mathsf {PCIP}$$
for
$$\mathsf {NP}$$
for which the
$$\mathsf {FSKM}$$
protocol is unsound no matter what
$$\mathsf {CRHF}$$
and Fiat-Shamir hash function is used. This result is unconditional (i.e., does not rely on any cryptographic assumptions).
Put together, our results show that the soundness of
$$\mathsf {FSKM}$$
must rely on some special structure of both the
$$\mathsf {CRHF}$$
and
$$\mathsf {PCP}$$
that underlie Kilian’s protocol. We believe these negative results may cast light on how to securely instantiate the
$$\mathsf {FSKM}$$
protocol by a synergistic choice of the
$$\mathsf {PCP}$$
,
$$\mathsf {CRHF}$$
, and Fiat-Shamir hash function.

#### Program Committees

- TCC 2020
- Eurocrypt 2019

#### Coauthors

- James Bartusek (1)
- Alexander R. Block (2)
- Elette Boyle (1)
- Liron Bronfman (1)
- Ran Canetti (2)
- Yilei Chen (1)
- Ofer Grossman (1)
- Ariel Hamlin (1)
- Fermi Ma (1)
- Mariana Raykova (1)
- Silas Richelson (1)
- Alon Rosen (2)
- Ron D. Rothblum (3)
- Pratik Soni (2)
- Mor Weiss (2)
- Daniel Wichs (1)
- Eylon Yogev (1)