Zero-Knowledge Proofs from Information-Theoretic Proof Systems - Part I

In this two-part extended blog post I will discuss a modular approach to the design of efficient zero-knowledge proof systems that aims at maximizing the separation between the “information-theoretic” and the “cryptographic” ingredients. While this approach is already practiced, it could arguably be applied more often and more systematically. The post is loosely based on recent talks I gave, including one at the 2nd ZKProof Workshop. Shorter expositions of this kind can be found in Section 2 of the ZKProof Community Reference document, Section 2 of the BBCGI19 paper and Section 5 of the BunzFS20 paper.

The growing number of competing proposals for practical zero-knowledge and/or succinct proof systems makes it easy to get confused about how these different systems compare to each other. One reason such comparisons are difficult is the multitude of application scenarios, implementation details, efficiency desiderata, cryptographic assumptions, and trust models. To make things worse, such systems are typically offered as a “package deal” that makes it difficult to apply a mix-and-match approach for finding the best combination of the underlying ideas in the context of a given application.

This calls for a modular approach that allows for an easier navigation in the huge design space. A higher level of modularity and abstraction is useful for capturing technical ideas in a way that makes them more broadly applicable, beyond the setting in which they were originally introduced. This can help us avoid reinvention of the same ideas in related contexts.

To make the post relatively self-contained, I would like to give some background on the kinds of zero-knowledge proof systems we will be interested in. I will also give a high-level overview of theoretical research in this area that provides the foundations, as well as a useful toolbox, for the recent practice-oriented research.

The goal of a zero-knowledge proof is specified by an NP-relation $R(x,w)$, where $x$ is referred to as a statement (or sometimes an input) and $w$ as a witness. A zero-knowledge proof for $R$ is a protocol that specifies the rules for an interaction between a prover and a verifier, both of which run in polynomial time and can toss coins. The prover and the verifier share a statement $x$ as common input, and the prover additionally knows a witness $w$ such that $(x,w)\in R$. One can think of $w$ as a “classical proof” that the statement $x$ is in the language $L=\{ x\,:\, \exists w \, (x,w)\in R\}$. However, instead of simply sending $w$ to the verifier, the prover would like to convince the verifier that $x\in L$ without revealing information about $w$. A zero-knowledge proof protocol for $R$ should satisfy the following, loosely stated, requirements:

This informal definition leaves some details unspecified, such as the allowable running times of a malicious prover and the quality of the simulation. It also ignores composition-related issues. See Chapter 4 of Goldreich’s textbook for a more rigorous treatment.

There are several important variations and extra features that will play a role in the following.

Proofs vs. arguments. The original notion of zero-knowledge proofs requires soundness to hold against computationally unbounded malicious provers. However, it is often useful to consider proof systems whose soundness is restricted to hold only against efficient (e.g., polynomial-time) provers. Such computationally sound proof systems are often referred to as arguments. Here I will typically ignore this distinction and use the term “proof” even in the case of computational soundness.

Proofs of knowledge. The soundness requirement is often replaced by a stronger proof of knowledge requirement, which captures the intuitive property that any prover who can convince the verifier of the truth of a statement $x$ (with better probability than the soundness error) must “know” a valid witness $w$ such that $R(x,w)$ holds. Here we will mainly focus on the simpler soundness requirement, though the concrete proof systems discussed below will in fact be proofs of knowledge.

Non-interactive proofs. A particularly appealing type of proof system is a non-interactive zero-knowledge (NIZK) proof, in which the protocol involves a single message from the prover to the verifier. This message may depend on a common reference string (CRS) that can either be uniformly random (URS) or structured (SRS). Here a long CRS can be generated together with a short verification key to speed up verification, and the zero-knowledge simulator is allowed to generate the reference string together with the simulated proof. Whereas there are simple (but unproven) heuristics for generating a URS without a trusted setup and without compromising security, there are no similar heuristics for generating an SRS. Instead, the SRS is typically generated using a large-scale secure multiparty computation protocol, a process sometimes referred to as an “MPC ceremony.”

A powerful technique for converting interactive proof systems into non-interactive ones is the Fiat-Shamir transform. This technique applies to the class of public-coin protocols, where the verifier’s role is restricted to generating and sending random messages, and essentially amounts to having the prover generate each verifier’s message by applying a hash function to the protocol’s transcript up to this message. While the security of the transformation can be proved in the random oracle model, which models the hash function as a perfectly random function, when instantiated with real hash functions the security becomes heuristic. An advantage of such non-interactive proof systems is that they are transparent in the sense that they avoid the need for a trusted setup by only requiring a URS, which can be eliminated in practice. See “state of the art” below for further discussion.

Designated-verifier proofs. The NIZK protocols discussed above have the appealing feature of being publicly verifiable, as the verifier has no secret state. An alternative setting is that of a designated-verifier NIZK, in which the CRS is a public key that corresponds to a secret verification key owned by the designated verifier, and can typically be securely generated by the verifier alone. Proofs generated using this public key can only be verified by the designated verifier. An even more liberal setting is that of NIZK with a correlated randomness setup (sometimes referred to as preprocessing NIZK). In this setting, a designated verifier and a designated prover share a pair $(k_P,k_V)$ of correlated secret keys. Proofs can be generated using $k_P$ and verified using $k_V$.

Succinct proofs. A final and very important goal in the design of proof systems is optimizing their efficiency. Here the main focus is on two efficiency measures that are typically (but not always) correlated: communication and verifier’s computation. Optimizing these measures is meaningful even for proof systems without the zero knowledge property. The baseline is the simple “classical” proof system in which the prover sends $w$ to the verifier, who checks that $R(x,w)$ indeed holds. This may be unsatisfactory in terms of both communication complexity and verifier’s running time. A succinct proof system is one that has better communication complexity. The term “succinct” is typically also associated with fast verification, requiring that the verifier’s running time be smaller than the time required for computing $R$, possibly given preprocessing that may depend on $R$ but not on the statement $x$. Here we will use this term to refer only to low communication complexity by default. The term succinct non-interactive argument, commonly abbreviated as SNARG, refers to a non-interactive, computationally sound proof system that satisfies the succinctness requirement. A zk-SNARG additionally satisfies zero knowledge, and a (zk-)SNARK additionally has the proof of knowledge property. As most succinct proof systems can be modified to realize the extra zero knowledge requirement with little extra cost, we will assume by default that all proof systems are zero knowledge even when we do not say it explicitly. However, most of this post is relevant also to succinct proof systems without zero knowledge. Finally, while we will mostly ignore here the proof of knowledge property, it is satisfied by almost all known proof systems, sometimes under stronger assumptions, and is important for many applications.

What do we know about the existence of zero-knowledge proofs for general NP-relations? Let me briefly summarize where we stand from a crude “feasibility” standpoint. More refined efficiency issues will be discussed later. Shortly after the introduction of zero-knowledge proofs by Goldwasser, Micali, and Rackoff in the mid-1980s, the first general construction was given by Goldreich, Micali, and Wigderson (see also Chapter 4 of Goldreich’s texbook). This construction, which will be described below, can use any cryptographic commitment scheme, which in turn can be based on one-way functions. On the other hand, Ostrovsky and Wigderson showed that a weak flavor of one-way functions is also necessary for non-trivial zero-knowledge. This means that a (very mild) cryptographic assumption is necessary and sufficient for the existence of general zero-knowledge proofs.

In the non-interactive setting, all current protocols require much stronger cryptographic assumptions. Originating from the work of Blum, Feldman, and Micali that introduced NIZK proofs, there has been a large body of work on diversifying these assumptions. This is an active area of research with some exciting recent results: see here, and here, and here. At this point in time, NIZK proofs for NP can be based on most of the standard cryptographic assumptions that are known to imply public-key encryption. Notable exceptions are assumptions related to the discrete logarithm problem.

The above state of the art is good, since it gives us a high degree of confidence that general NIZK protocols do exist. But it also leaves a gap between the current “provable” constructions and ones that rely on instantiating the Fiat-Shamir transform. It is commonly believed that this heuristic is good enough for practical proof systems and hash functions that were not designed to defeat it. This holds even with hash functions that are not known to imply public-key cryptography. However, we do not have good evidence in this direction, and there are negative results that rule out a generic approach for instantiating a random oracle with a concrete hash function, even in the specific context of the Fiat-Shamir transform (when applied to arguments rather than proofs). See this and this recent works for a survey of this direction. Understanding the minimal cryptographic assumptions that suffice for NIZK is an intriguing question that will surely generate a lot of interesting future research.

For succinct proof systems, the state of provable constructions is considerably worse. Things are not too bad in the interactive setting, where collision-resistant hash functions suffice for obtaining succinct proof systems for NP. (This is considered a standard and mild cryptographic assumption, albeit stronger than one-way functions that suffice for non-succinct zero-knowledge proofs.) In the non-interactive setting, all known constructions are either cast in idealized models (such as the random oracle model or the generic group model) or alternatively are based on strong “extractability” assumptions such as knowledge-of-exponent assumptions. The latter seem hard to validate and are in some cases likely to be false. The algebraic group model is a weaker version of the generic group model that can potentially be instantiated and may serve as a cleaner substitute to concrete extractability assumptions.

Can SNARGs be based on standard cryptographic assumptions? Gentry and Wichs gave negative evidence that effectively serves as a barrier. They showed that, in some well-defined sense, “standard” assumptions and proof techniques cannot imply SNARGs with adaptive soundness, namely soundness that holds even when the statement can depend on the CRS. The goal of basing different flavors of SNARGs on standard cryptographic assumptions remains an important challenge in the theory of cryptography. Progress on this question is likely to require new techniques that have benefits beyond the goal of provable security. See here, here, here, and here for a very partial sample of results along this line.

This post is about separating the “cryptographic” part of a proof system from the “information-theoretic” part. Before switching to a more abstract level, let me put this in the context of practical zero-knowledge proof systems. Such systems are often divided into two parts: (1) a “front-end” compiler converting a specification of an NP-relation $R$ (e.g., using a C program) into a “zero-knowledge friendly” representation $\hat R$ (such as an arithmetic circuit or a rank-1 constraint system — R1CS); (2) a “back-end” compiler converting $\hat R$ to a zero-knowledge proof protocol for $R$. The two components are related in that the zero-knowledge friendly representation is tailored to the back-end compiler.

Here we will not consider front-end compilers. Instead, we are interested in further breaking the back-end compiler into two parts: (2a) converting $\hat R$ into a (zero-knowledge) information-theoretic proof system for $R$, and (2b) using a cryptographic compiler for converting the information-theoretic proof system into a usable zero-knowledge proof protocol for $R$. Let me explain what each part means.

Information-theoretic proof system. Such a proof system, sometimes referred to as a probabilistically checkable proof (PCP), is information-theoretic in the sense that it provides soundness and zero knowledge guarantees even when the prover and the verifier are computationally unbounded. To make this possible, the proof system can make idealized assumptions that are difficult to enforce via direct interaction. For instance, it may allow the prover to generate a long proof vector and then only grant the verifier restricted access to this vector, where the access pattern is independent of the proof. Enforcing this restricted access via direct interaction is outside the scope of an information-theoretic proof system. (The classical notion of interactive proofs does not make any idealized assumptions; however such proofs are much weaker than the information-theoretic proof systems considered in this work.) The idealized assumptions typically make information-theoretic proof systems useless as standalone objects. On the other hand, they allow us to construct them unconditionally, without relying on cryptographic assumptions. We will discuss several kinds of information-theoretic proof systems with incomparable features. The different kinds of proof systems vary in the restrictions they impose on the verifier’s access to the proof and the amount of interaction. We will also discuss information-theoretic compilers that convert one type of information-theoretic proof system into another.

Cryptographic compiler. The cryptographic compiler removes the idealized assumptions that underly the information-theoretic proof system by transforming it into a protocol that involves direct interaction between the prover and the verifier. This is done by using cryptographic primitives, such as a collision-resistant hash function, or alternatively idealized primitives that replace them, such as a random oracle or a generic bilinear group. Both types of primitives may come with some (possibly heuristic) concrete instantiation, such as a concrete hash function or pairing-friendly elliptic curve. Unlike the underlying information-theoretic proof system, the protocol obtained by the cryptographic compiler is only secure with respect to a computationally bounded prover and/or verifier. This security will typically be based on a cryptographic assumption. A possible exception is when using idealized primitives. In this case, security can be unconditional, but it is still computational in the sense that it bounds the number of queries (or “oracle calls”) made to the primitive. The cryptographic compiler may also provide extra desirable properties, such as eliminating interaction, shrinking the size of some of the messages, or even adding a zero knowledge feature to an information-theoretic proof system that doesn’t have it.

Advantages of the separation. Separating information-theoretic proof systems from cryptographic compilers can serve multiple purposes. It makes protocol design conceptually simpler by breaking it into two modular parts, where each part can be analyzed, optimized, and implemented separately. This facilitates a systematic exploration of the design space in search of the best solution for the task at hand. It enables useful mixing and matching of different instantiations of the two components. For instance, the same information-theoretic proof system can be paired with different cryptographic compilers to give useful tradeoffs between efficiency, security, and setup assumptions. This makes it easier to port technical insights and optimization ideas between different types of proof systems. Finally, information-theoretic proof systems serve as cleaner objects of study than their computationally secure counterparts. In particular, they are better targets for lower bound efforts, which can lead to new insights that often result in better upper bounds.

To illustrate the above modular approach, let’s revisit the first construction of a zero-knowledge proof system for NP.

The 3-coloring problem. The proof system is described for the specific 3-coloring relation $R_{\sf 3COL}$, where the statement is an undirected graph $G=(V,E)$, the witness is a mapping $c:V\to\{1,2,3\}$ specifying a coloring of each node by one of three colors, and $R$ tests whether the coloring is valid. Concretely, $(G,c)\in R_{\sf 3COL}$ if $c(u)\neq c(v)$ whenever $(u,v)\in E$. The relation $R_{\sf 3COL}$ corresponds to the NP-complete problem of deciding whether a graph $G$ is 3-colorable. This implies that a zero-knowledge proof for any NP-relation $R$ can be obtained from a zero-knowledge proof for $R_{\sf 3COL}$ by having the prover and the verifier locally apply a polynomial-time reduction to convert their inputs for $R$ into inputs for $R_{\sf 3COL}$.

The protocol. The zero-knowledge proof for $R_{\sf 3COL}$ proceeds as follows.

Analysis. The above protocol satisfies the completeness property, since if the coloring $c$ is valid then so is its permuted version $c’$, and so an honest prover will always successfully open two distinct colors in $c’$. It intuitively satisfies the zero knowledge requirement because the only colors not hidden by the commitments are the opened colors $(c'(u),c'(v))$, which can be simulated by choosing two distinct but otherwise random colors. Note that this holds even for a malicious verifier, who can choose $u$ and $v$ arbitrarily, assuming that the prover checks that the pair $(u,v)$ sent by the verifier is indeed a valid edge; this check is necessary, since otherwise the verifier can learn whether the two (disconnected) nodes $u$ and $v$ have the same color in $c$. The simulation is easy to formalize if commitments are implemented by a physical locked box, but is considerably more subtle when using a computationally hiding cryptographic commitment scheme.

An abstraction? The above protocol, while simple and elegant, leaves much to be desired in terms of efficiency. There are two sources of overhead. The first is a Cook-Levin reduction from a “useful” NP-relation $R$ (say, the satisfiability of a Boolean or arithmetic circuit) to $R_{\sf 3COL}$. The second is the overhead of amplifying soundness, which grows linearly with $|E|$. Even in terms of simplicity, while the analysis of the protocol is quite straightforward when using ideal commitments, this is not the case when using their cryptographic implementation. Should this analysis be redone from scratch for a similar protocol based on a different NP-complete problem, say graph Hamiltonicity? Abstraction can be helpful towards addressing both issues.

The combinatorial core of the above protocol can be abstracted by a simple kind of information-theoretic proof system that I will refer to as a zero-knowledge probabilistically checkable proof (zk-PCP). (Here I am using this term to refer to a specific, arguably the simplest, flavor; other flavors of zk-PCP will be discussed later.) In a zk-PCP for an NP-relation $R$, the prover computes a probabilistic polynomial time mapping from a statement-witness pair $(x,w)$ to a proof string $\pi\in\Sigma^m$. In the above example, $\pi$ is a string of length $m=|V|$ over $\Sigma=\{1,2,3\}$ comprised of the values $c'(v)$ for $v\in V$, where the randomness is over the permutation $\phi$ used to convert $c$ into $c’$. The verifier decides whether to accept or reject by querying a randomly chosen subset of the symbols of $\pi$. More concretely, the verifier’s algorithm is specified by a randomized mapping from an instance $x$ to a subset $Q\subset[m]$ of queried symbols, and a decision predicate $D(x,Q,\pi_Q)$ deciding whether to accept or reject based on the contents of the queried symbols. In the above example, $Q$ is uniformly distributed over sets of size 2 corresponding to edges in $E$, and $D$ accepts if the two queried symbols are distinct. We assume that one can efficiently recognize whether a set $Q$ can be generated by an honest verifier on a given input $x$.

The completeness, soundness, and zero knowledge properties of a zk-PCP are defined as expected, where the zero-knowledge simulator is required by default to perfectly sample the view $(Q,\pi_Q)$ of an honest verifier given $x$ alone. The basic version of the zk-PCP for $R_{\sf 3COL}$ has a high soundness error of $1-1/|E|$. Soundness can be amplified, while respecting zero knowledge, by concatenating independently generated proofs $\pi^{(i)}$ and querying them independently. Note that making multiple queries to the same $\pi$ would compromise zero knowledge.