## CryptoDB

### Ron D. Rothblum

#### Publications

**Year**

**Venue**

**Title**

2021

EUROCRYPT

Public-Coin Statistical Zero-Knowledge Batch Verification against Malicious Verifiers
📺
Abstract

Suppose that a problem $\Pi$ has a statistical zero-knowledge (SZK) proof with communication complexity $m$. The question of batch verification for SZK asks whether one can prove that $k$ instances $x_1,\dots,x_k$ all belong to $\Pi$ with a statistical zero-knowledge proof whose communication complexity is better than $k \cdot m$ (which is the complexity of the trivial solution of executing the original protocol independently on each input).
In a recent work, Kaslasi et al. (TCC, 2020) constructed such a batch verification protocol for any problem having a non-interactive SZK (NISZK) proof-system. Two drawbacks of their result are that their protocol is private-coin and is only zero-knowledge with respect to the honest verifier.
In this work, we eliminate these two drawbacks by constructing a public-coin malicious-verifier SZK protocol for batch verification of NISZK. Similarly to the aforementioned prior work, the communication complexity of our protocol is $(k+poly(m)) \cdot polylog(k,m)$.

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.

2021

JOFC

Toward Non-interactive Zero-Knowledge Proofs for NP from LWE
Abstract

Non-interactive zero-knowledge ( $$\mathsf {NIZK}$$ NIZK ) is a fundamental primitive that is widely used in the construction of cryptographic schemes and protocols. Our main result is a reduction from constructing $$\mathsf {NIZK}$$ NIZK proof systems for all of $$\mathbf {NP}$$ NP based on $$\mathsf {LWE}$$ LWE , to constructing a $$\mathsf {NIZK}$$ NIZK proof system for a particular computational problem on lattices, namely a decisional variant of the bounded distance decoding ( $$\mathsf {BDD}$$ BDD ) problem. That is, we show that assuming $$\mathsf {LWE}$$ LWE , every language $$L \in \mathbf {NP}$$ L ∈ NP has a $$\mathsf {NIZK}$$ NIZK proof system if (and only if) the decisional $$\mathsf {BDD}$$ BDD problem has a $$\mathsf {NIZK}$$ NIZK proof system. This (almost) confirms a conjecture of Peikert and Vaikuntanathan (CRYPTO, 2008). To construct our $$\mathsf {NIZK}$$ NIZK proof system, we introduce a new notion that we call prover-assisted oblivious ciphertext sampling ( $$\mathsf {POCS}$$ POCS ), which we believe to be of independent interest. This notion extends the idea of oblivious ciphertext sampling , which allows one to sample ciphertexts without knowing the underlying plaintext. Specifically, we augment the oblivious ciphertext sampler with access to an (untrusted) prover to help it accomplish this task. We show that the existence of encryption schemes with a $$\mathsf {POCS}$$ POCS procedure, as well as some additional natural requirements, suffices for obtaining $$\mathsf {NIZK}$$ NIZK proofs for $$\mathbf {NP}$$ NP . We further show that such encryption schemes can be instantiated based on $$\mathsf {LWE}$$ LWE , assuming the existence of a $$\mathsf {NIZK}$$ NIZK proof system for the decisional $$\mathsf {BDD}$$ BDD problem.

2020

TCC

Batch Verification for Statistical Zero Knowledge Proofs
📺
Abstract

A statistical zero-knowledge proof (SZK) for a problem $\Pi$ enables a computationally unbounded prover to convince a polynomial-time verifier that $x \in \Pi$ without revealing any additional information about $x$ to the verifier, in a strong information-theoretic sense.
Suppose, however, that the prover wishes to convince the verifier that $k$ separate inputs $x_1,\dots,x_k$ all belong to $\Pi$ (without revealing anything else). A naive way of doing so is to simply run the SZK protocol separately for each input. In this work we ask whether one can do better -- that is, is efficient batch verification possible for SZK?
We give a partial positive answer to this question by constructing a batch verification protocol for a natural and important subclass of SZK -- all problems $\Pi$ that have a non-interactive SZK protocol (in the common random string model). More specifically, we show that, for every such problem $\Pi$, there exists an honest-verifier SZK protocol for batch verification of $k$ instances, with communication complexity $poly(n) + k \cdot poly(\log{n},\log{k})$, where $poly$ refers to a fixed polynomial that depends only on $\Pi$ (and not on $k$). This result should be contrasted with the naive solution, which has communication complexity $k \cdot poly(n)$.
Our proof leverages a new NISZK-complete problem, called Approximate Injectivity, that we find to be of independent interest. The goal in this problem is to distinguish circuits that are nearly injective, from those that are non-injective on almost all inputs.

2020

TCC

Batch Verification and Proofs of Proximity with Polylog Overhead
📺
Abstract

Suppose Alice wants to convince Bob of the correctness of k NP statements. Alice could send k witnesses to Bob, but as k grows the communication becomes prohibitive. Is it possible to convince Bob using smaller communication (without making cryptographic assumptions or bounding the computational power of a malicious Alive)? This is the question of batch verification for NP statements. Our main result is a new interactive proof protocol for verifying the correctness of k UP statements (NP statements with a unique witness) using communication that is poly-logarithmic in k (and a fixed polynomial in the length of a single witness).
This result is obtained by making progress on a different question in the study of interactive proofs. Suppose Alice wants to convince Bob that a huge dataset has some property. Can this be done if Bob can't even read the entire input? In other words, what properties can be verified in sublinear time? An Interactive Proof of Proximity guarantees that Bob accepts if the input has the property, and rejects if the input is far (say in Hamming distance) from having the property. Two central complexity measures of such a protocol are the query and communication complexities (which should both be sublinear). For every query parameter $q$, and for every language in logspace uniform NC, we construct an interactive proof of proximity with query complexity $q$ and communication complexity $(n/q) \cdot \polylog(n)$.
Both results are optimal up to poly-logarithmic factors, under reasonable complexity-theoretic or cryptographic assumptions. The second result, which is our main technical contribution, builds on a distance amplification technique introduced in a beautiful recent work of Ben-Sasson, Kopparty and Saraf [CCC 2018].

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

PKC

Towards Non-Interactive Zero-Knowledge for NP from LWE
Abstract

Non-interactive zero-knowledge (
$$\mathsf {NIZK}$$
) is a fundamental primitive that is widely used in the construction of cryptographic schemes and protocols. Despite this, general purpose constructions of
$$\mathsf {NIZK}$$
proof systems are only known under a rather limited set of assumptions that are either number-theoretic (and can be broken by a quantum computer) or are not sufficiently well understood, such as obfuscation. Thus, a basic question that has drawn much attention is whether it is possible to construct general-purpose
$$\mathsf {NIZK}$$
proof systems based on the learning with errors (
$$\mathsf {LWE}$$
) assumption.Our main result is a reduction from constructing
$$\mathsf {NIZK}$$
proof systems for all of
$$\mathbf {NP}$$
based on
$$\mathsf {LWE}$$
, to constructing a
$$\mathsf {NIZK}$$
proof system for a particular computational problem on lattices, namely a decisional variant of the Bounded Distance Decoding (
$$\mathsf {BDD}$$
) problem. That is, we show that assuming
$$\mathsf {LWE}$$
, every language
$$L \in \mathbf {NP}$$
has a
$$\mathsf {NIZK}$$
proof system if (and only if) the decisional
$$\mathsf {BDD}$$
problem has a
$$\mathsf {NIZK}$$
proof system. This (almost) confirms a conjecture of Peikert and Vaikuntanathan (CRYPTO, 2008).To construct our
$$\mathsf {NIZK}$$
proof system, we introduce a new notion that we call prover-assisted oblivious ciphertext sampling (
$$\mathsf {POCS}$$
), which we believe to be of independent interest. This notion extends the idea of oblivious ciphertext sampling, which allows one to sample ciphertexts without knowing the underlying plaintext. Specifically, we augment the oblivious ciphertext sampler with access to an (untrusted) prover to help it accomplish this task. We show that the existence of encryption schemes with a
$$\mathsf {POCS}$$
procedure, as well as some additional natural requirements, suffices for obtaining
$$\mathsf {NIZK}$$
proofs for
$$\mathbf {NP}$$
. We further show that such encryption schemes can be instantiated based on
$$\mathsf {LWE}$$
, assuming the existence of a
$$\mathsf {NIZK}$$
proof system for the decisional
$$\mathsf {BDD}$$
problem.

2019

EUROCRYPT

Reusable Designated-Verifier NIZKs for all NP from CDH
📺
Abstract

Non-interactive zero-knowledge proofs (NIZKs) are a fundamental cryptographic primitive. Despite a long history of research, we only know how to construct NIZKs under a few select assumptions, such as the hardness of factoring or using bilinear maps. Notably, there are no known constructions based on either the computational or decisional Diffie-Hellman (CDH/DDH) assumption without relying on a bilinear map.In this paper, we study a relaxation of NIZKs in the designated verifier setting (DV-NIZK), in which the public common-reference string is generated together with a secret key that is given to the verifier in order to verify proofs. In this setting, we distinguish between one-time and reusable schemes, depending on whether they can be used to prove only a single statement or arbitrarily many statements. For reusable schemes, the main difficulty is to ensure that soundness continues to hold even when the malicious prover learns whether various proofs are accepted or rejected by the verifier. One-time DV-NIZKs are known to exist for general NP statements assuming only public-key encryption. However, prior to this work, we did not have any construction of reusable DV-NIZKs for general NP statements from any assumption under which we didn’t already also have standard NIZKs.In this work, we construct reusable DV-NIZKs for general NP statements under the CDH assumption, without requiring a bilinear map. Our construction is based on the hidden-bits paradigm, which was previously used to construct standard NIZKs. We define a cryptographic primitive called a hidden-bits generator (HBG), along with a designated-verifier variant (DV-HBG), which modularly abstract out how to use this paradigm to get both standard NIZKs and reusable DV-NIZKs. We construct a DV-HBG scheme under the CDH assumption by relying on techniques from the Cramer-Shoup hash-proof system, and this yields our reusable DV-NIZK for general NP statements under CDH.We also consider a strengthening of DV-NIZKs to the malicious designated-verifier setting (MDV-NIZK) where the setup consists of an honestly generated common random string and the verifier then gets to choose his own (potentially malicious) public/secret key pair to generate/verify proofs. We construct MDV-NIZKs under the “one-more CDH” assumption without relying on bilinear maps.

2019

CRYPTO

New Constructions of Reusable Designated-Verifier NIZKs
📺
Abstract

Non-interactive zero-knowledge arguments (NIZKs) for $$\mathsf {NP}$$ are an important cryptographic primitive, but we currently only have instantiations under a few specific assumptions. Notably, we are missing constructions from the learning with errors (LWE) assumption, the Diffie-Hellman (CDH/DDH) assumption, and the learning parity with noise (LPN) assumption.In this paper, we study a relaxation of NIZKs to the designated-verifier setting (DV-NIZK), where a trusted setup generates a common reference string together with a secret key for the verifier. We want reusable schemes, which allow the verifier to reuse the secret key to verify many different proofs, and soundness should hold even if the malicious prover learns whether various proofs are accepted or rejected. Such reusable DV-NIZKs were recently constructed under the CDH assumption, but it was open whether they can also be constructed under LWE or LPN.We also consider an extension of reusable DV-NIZKs to the malicious designated-verifier setting (MDV-NIZK). In this setting, the only trusted setup consists of a common random string. However, there is also an additional untrusted setup in which the verifier chooses a public/secret key needed to generate/verify proofs, respectively. We require that zero-knowledge holds even if the public key is chosen maliciously by the verifier. Such reusable MDV-NIZKs were recently constructed under the “one-more CDH” assumption, but constructions under CDH/LWE/LPN remained open.In this work, we give new constructions of (reusable) DV-NIZKs and MDV-NIZKs using generic primitives that can be instantiated under CDH, LWE, or LPN.

2019

TCC

Statistical Difference Beyond the Polarizing Regime
Abstract

The polarization lemma for statistical distance (
$${\text {SD}}$$
), due to Sahai and Vadhan (JACM, 2003), is an efficient transformation taking as input a pair of circuits
$$(C_0,C_1)$$
and an integer k and outputting a new pair of circuits
$$(D_0,D_1)$$
such that if
$${\text {SD}}(C_0,C_1) \ge \alpha $$
then
$${\text {SD}}(D_0,D_1) \ge 1-2^{-k}$$
and if
$${\text {SD}}(C_0,C_1) \le \beta $$
then
$${\text {SD}}(D_0,D_1) \le 2^{-k}$$
. The polarization lemma is known to hold for any constant values
$$\beta < \alpha ^2$$
, but extending the lemma to the regime in which
$$\alpha ^2 \le \beta < \alpha $$
has remained elusive. The focus of this work is in studying the latter regime of parameters. Our main results are: 1.Polarization lemmas for different notions of distance, such as Triangular Discrimination (
$${{\,\mathrm{TD}\,}}$$
) and Jensen-Shannon Divergence (
$${{\,\mathrm{JS}\,}}$$
), which enable polarization for some problems where the statistical distance satisfies
$$ \alpha ^2< \beta < \alpha $$
. We also derive a polarization lemma for statistical distance with any inverse-polynomially small gap between
$$ \alpha ^2 $$
and
$$ \beta $$
(rather than a constant).2.The average-case hardness of the statistical difference problem (i.e., determining whether the statistical distance between two given circuits is at least
$$\alpha $$
or at most
$$\beta $$
), for any values of
$$\beta < \alpha $$
, implies the existence of one-way functions. Such a result was previously only known for
$$\beta < \alpha ^2$$
.3.A (direct) constant-round interactive proof for estimating the statistical distance between any two distributions (up to any inverse polynomial error) given circuits that generate them. Proofs of closely related statements have appeared in the literature but we give a new proof which we find to be cleaner and more direct.

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.

2018

CRYPTO

From Laconic Zero-Knowledge to Public-Key Cryptography
📺
Abstract

Since its inception, public-key encryption (
$$\mathsf {PKE}$$
PKE) has been one of the main cornerstones of cryptography. A central goal in cryptographic research is to understand the foundations of public-key encryption and in particular, base its existence on a natural and generic complexity-theoretic assumption. An intriguing candidate for such an assumption is the existence of a cryptographically hard language .In this work we prove that public-key encryption can be based on the foregoing assumption, as long as the (honest) prover in the zero-knowledge protocol is efficient and laconic. That is, messages that the prover sends should be efficiently computable (given the witness) and short (i.e., of sufficiently sub-logarithmic length). Actually, our result is stronger and only requires the protocol to be zero-knowledge for an honest-verifier and sound against computationally bounded cheating provers.Languages in with such laconic zero-knowledge protocols are known from a variety of computational assumptions (e.g., Quadratic Residuocity, Decisional Diffie-Hellman, Learning with Errors, etc.). Thus, our main result can also be viewed as giving a unifying framework for constructing
$$\mathsf {PKE}$$
PKE which, in particular, captures many of the assumptions that were already known to yield
$$\mathsf {PKE}$$
PKE.We also show several extensions of our result. First, that a certain weakening of our assumption on laconic zero-knowledge is actually equivalent to
$$\mathsf {PKE}$$
PKE, thereby giving a complexity-theoretic characterization of
$$\mathsf {PKE}$$
PKE. Second, a mild strengthening of our assumption also yields a (2-message) oblivious transfer protocol.

2013

JOFC

Enhancements of Trapdoor Permutations
Abstract

We take a closer look at several enhancements of the notion of trapdoor permutations. Specifically, we consider the notions of enhanced trapdoor permutation (Goldreich, Foundation of Cryptography: Basic Applications, 2004) and doubly enhanced trapdoor permutation (Goldreich, Computational Complexity: A Conceptual Perspective, 2011) as well as intermediate notions (Rothblum, A Taxonomy of Enhanced Trapdoor Permutations, 2010). These enhancements arose in the study of Oblivious Transfer and NIZK, but they address natural concerns that may arise also in other applications of trapdoor permutations. We clarify why these enhancements are needed in such applications, and show that they actually suffice for these needs.

#### Program Committees

- Eurocrypt 2020
- Crypto 2018
- TCC 2017

#### Coauthors

- James Bartusek (1)
- Itay Berman (3)
- Alexander R. Block (2)
- Liron Bronfman (1)
- Ran Canetti (1)
- Yilei Chen (1)
- Gil Cohen (1)
- Ivan Damgård (1)
- Akshay Degwekar (3)
- Yevgeniy Dodis (1)
- Oded Goldreich (1)
- Shai Halevi (1)
- Justin Holmgren (3)
- Yuval Ishai (1)
- Abhishek Jain (1)
- Yael Tauman Kalai (3)
- Inbar Kaslasi (2)
- Dakshita Khurana (1)
- Jonas Kölker (1)
- Alex Lombardi (1)
- Fermi Ma (1)
- Peter Bro Miltersen (1)
- Willy Quach (2)
- Ran Raz (1)
- Leonid Reyzin (1)
- Alon Rosen (2)
- Guy N. Rothblum (3)
- Adam Sealfon (3)
- Pratik Soni (2)
- Katerina Sotiraki (2)
- Prashant N. Vasudevan (1)
- Prashant Nalini Vasudevan (4)
- Daniel Wichs (3)
- David J. Wu (1)