Zero-knowledge proof

A zero-knowledge proof is an interactive protocol between a prover $P$ and a verifier $V$ in which $P$ convinces $V$ that a statement $x$ belongs to a language $L$ without revealing anything beyond the fact that $x\in L$. Introduced by Goldwasser, Micali, and Rackoff — GMR85.

Syntax

A zero-knowledge proof system for a language $L\subseteq \{0,1{\}}^{\ast }$ is an interactive protocol $(P,V)$ where:

• $P$ receives as input $(x,w)$ where $w$ is a witness for $x\in L$
• $V$ receives input $x$ and outputs $\mathrm{accept}$ or $\mathrm{reject}$
• The transcript of the interaction is a sequence of messages $({\alpha }_1,{\beta }_1,\dots ,{\alpha }_k,{\beta }_k)$

Properties

Completeness

If $x\in L$ and $P$ follows the protocol honestly, then $V$ accepts with probability 1 (or $1-\mathrm{negl}(\lambda )$ for statistical completeness).

Soundness

If $x\notin L$, then for all computationally unbounded $P^{\ast }$: $\mathrm{Pr}[V\text{ accepts in }⟨P^{\ast }(x),V(x)⟩]\le \mathrm{negl}(\lambda ).$

If this holds only for efficient $P^{\ast }$, the system is an argument system.

Knowledge soundness (Proof of knowledge)

A stronger notion: there exists an efficient extractor $E$ such that if $P^{\ast }$ convinces $V$ with non-negligible probability, then $E^{P^{\ast }}(x)$ outputs a valid witness $w$ for $x\in L$ with non-negligible probability.

Zero-knowledge

The interaction reveals nothing beyond $x\in L$. Formally, for every efficient verifier $V^{\ast }$ there exists an efficient simulator $\mathcal{S}$ such that for all $x\in L$, the distribution of $\mathcal{S}(x)$ is computationally (or statistically, or perfectly) indistinguishable from the view of $V^{\ast }$ in the real interaction $⟨P(x,w),V^{\ast }(x)⟩$ — GMR85.

Variations

Perfect / statistical / computational ZK

Depending on whether the simulator’s output is identically distributed, statistically close, or only computationally indistinguishable from the real transcript.

Honest-verifier ZK (HVZK)

Weaker form where the simulator only works against an honest verifier that picks challenges uniformly at random. Sufficient for many applications when combined with the Fiat-Shamir transform.

Sigma protocols

A sigma protocol ($\Sigma$-protocol) is a 3-message HVZK proof: (1) commitment $\alpha$ from prover; (2) random challenge $\beta$ from verifier; (3) response $\gamma$ from prover. Sigma protocols satisfy special soundness (two accepting transcripts with the same $\alpha$ but different $\beta$ yield a witness extractor) and HVZK. The Schnorr protocol for the discrete-logarithm relation is the canonical example — Sch91; its special soundness and perfect HVZK hold in every prime-order group, with no hardness assumption — standard.

Witness-indistinguishable (WI) proofs

Weaker than ZK: the verifier cannot distinguish which of multiple valid witnesses the prover used. WI proofs compose concurrently (unlike ZK proofs in general) and can be built without requiring any setup — FS90.

Zaps

A zap is a two-message public-coin witness-indistinguishable proof for an $\mathbf{NP}$-complete language, and hence, by Levin reductions, for every language in $\mathbf{NP}$, whose first message is a uniformly random string $\rho$ sent by the verifier; the verifier’s decision is a deterministic function of $x$, $\rho$ and the prover’s answer. Soundness holds against unbounded provers for all statements simultaneously: except with negligible probability over $\rho$, no $x\notin L$ has an accepting answer, so $\rho$ can be fixed once and reused for any number of statements. Witness indistinguishability holds for every first message: for every $\rho$, every $x$ and witnesses $w_0,w_1$ for $x$, the prover’s answers on $(\rho ,x,w_0)$ and $(\rho ,x,w_1)$ are computationally indistinguishable — DN00.

Statistical zap arguments

A two-message public-coin argument for an $\mathbf{NP}$-complete language whose first message is a uniformly random string $\rho$ sent by the verifier; unlike a zap, its soundness is computational and its witness indistinguishability statistical. Witness indistinguishability holds for every first message: for every $\rho$, every $x$ and witnesses $w_0,w_1$ for $x$, the prover’s messages on $(\rho ,x,w_0)$ and $(\rho ,x,w_1)$ are statistically close. Soundness is computational and non-adaptive: for every false statement $x$ fixed before $\rho$ is sampled, every efficient prover makes the verifier accept with negligible probability. Statistical zap arguments were introduced by BFJKS20 and GJJM20; this soundness notion is the one of BLNWW25, who construct them from LWE (Quasi-polynomially hard LWE ⇒ Statistical zap arguments).

Non-interactive zaps

A one-message witness-indistinguishable proof for an $\mathbf{NP}$-complete language with no setup or shared randomness. The verifier is deterministic and soundness is perfect: for every $x\notin L$ it rejects every message. For every statement $x$ and witnesses $w_0,w_1$ for $x$, the prover’s messages on $(x,w_0)$ and $(x,w_1)$ are computationally indistinguishable — BOV03, GOS06b.

Argument systems

Proof systems with only computational (not information-theoretic) soundness. Enables much more efficient constructions; see NIZK and SNARKs.

Constant-round public-coin zero-knowledge arguments

A zero-knowledge argument for an $\mathbf{NP}$-complete language, and hence, by Levin reductions, for every language in $\mathbf{NP}$, with a constant number of messages, public coins and negligible soundness error — Bar01. Without the restriction every language in $\mathbf{BPP}$ has one, in which the verifier decides alone — standard.

Three-message zero-knowledge arguments

A zero-knowledge argument for an $\mathbf{NP}$-complete language, and hence, by Levin reductions, for every language in $\mathbf{NP}$, with three messages and negligible soundness error. With a black-box simulator only languages in $\mathbf{BPP}$ have one, so constructions simulate non-black-box (Three-message black-box ZK ⊆ BPP) — GK96a.

Four-message zero-knowledge arguments

A zero-knowledge argument for an $\mathbf{NP}$-complete language, and hence for every language in $\mathbf{NP}$, with four messages and negligible soundness error, whose simulator may run in expected polynomial time — BJY97. A black-box simulator of a constant-round argument for a language outside $\mathbf{BPP}$ cannot run in strict polynomial time (constant-round black-box ZK with strict polynomial-time simulation ⊆ BPP) — BL02.

Concurrent zero-knowledge arguments

A zero-knowledge argument for an $\mathbf{NP}$-complete language that is concurrent zero-knowledge: for every efficient verifier that runs polynomially many sessions with independent prover instances on common input $x$, interleaving and scheduling their messages adaptively, an efficient simulator reproduces its joint view of all sessions — DNS98.

Statistical zero-knowledge arguments

An argument system whose zero-knowledge property is statistical: the simulator’s output is statistically close to the verifier’s view, so the view leaks nothing about the witness even to an unbounded distinguisher, while soundness holds only against efficient provers — BCC88.

Constant-round zero-knowledge proofs

A zero-knowledge proof (with soundness against unbounded provers) for an $\mathbf{NP}$-complete language, and hence, by Levin reductions, for every language in $\mathbf{NP}$, with a constant number of messages and negligible soundness error, whose simulator may run in expected polynomial time, as the black-box simulator of GK96b does — GK96b, BL02.

Concurrent zero-knowledge proofs

A zero-knowledge proof, sound against unbounded provers, for an $\mathbf{NP}$-complete language that is concurrent zero-knowledge in the sense of concurrent zero-knowledge arguments — DNS98.

Other results

• Zero-knowledge proofs were introduced together with a perfect zero-knowledge proof for the quadratic residuosity language $\{(N,a):a\in {\mathrm{QR}}_N\}$, which needs no hardness assumption — GMR85
• OWF ⇒ ZKP
  • A zero-knowledge proof for an $\mathbf{NP}$ relation can use a multi-party protocol for the relation only as a black box, which brings the communication down to $O(s)+\mathrm{poly}(k)$ for a circuit of size $s$ and security parameter $k$ (OWF ⇒ ZKP (MPC in the head)) — IKOS07
• Assuming secure probabilistic encryption, all languages in IP (= PSPACE) have computational ZK proofs — BGG+90; one-way functions suffice, since they give statistically binding commitments — HILL99, Naor91
• Zero knowledge for a language outside $\mathbf{BPP}$ implies auxiliary-input one-way functions (CZK ⊄ BPP ⇒ Auxiliary-input OWF) — OW93
• Auxiliary-input zero knowledge is preserved under sequential composition — GO94; the original definition without auxiliary input is not, and zero knowledge is not closed under parallel composition — GK96a
  • Assuming either almost-optimal hardness of search LWE or a circular-secure fully homomorphic encryption scheme with standard security, the quadratic residuosity protocol of GMR85 is not zero-knowledge when repeated in parallel; under either assumption the same paper gives NIZK arguments for $\mathbf{NP}$ in the common reference string model — CCH+19
• HVZK ⇒ NIZK (Fiat–Shamir)

Participates in

Builds on Zero-knowledge proof

• HVZK ⇒ NIZK (Fiat–Shamir) (via Honest-verifier ZK (HVZK))
• Non-interactive zap ⇒ Zap (via Non-interactive zaps)
• Zap + HSG ⇒ Non-interactive zaps (BOV) (via Zaps)

Produces Zero-knowledge proof

• Bilinear pairing + DLIN ⇒ Zaps (non-interactive) (via Non-interactive zaps)
• Claw-free permutations ⇒ Concurrent ZK proofs for NP in ω(log n) rounds (via Concurrent zero-knowledge proofs)
• Claw-free permutations ⇒ Constant-round ZK proofs for NP (Goldreich–Kahan) (via Constant-round zero-knowledge proofs)
• CRHF ⇒ Constant-round ZK argument (Barak) (via Constant-round public-coin zero-knowledge arguments)
• OWF ⇒ ZKP
• Injective OWF ⇒ Four-message ZK arguments for NP (fully black-box) (via Four-message zero-knowledge arguments)
• iO ⇒ Statistical ZK arguments for NP (via Statistical zero-knowledge arguments)
• NIZK ⇒ Zaps (Dwork–Naor) (via Zaps)
• Non-interactive zap ⇒ Zap (via Zaps)
• OWF ⇒ Concurrent ZK arguments for NP in ω(log n) rounds (via Concurrent zero-knowledge arguments)
• OWF ⇒ Four-message ZK arguments for NP (via Four-message zero-knowledge arguments)
• OWF ⇒ Statistical ZK arguments for NP (via Statistical zero-knowledge arguments)
• OWF ⇒ Constant-round WI proofs for NP (Feige–Shamir) (via Witness-indistinguishable (WI) proofs)
• OWF ⇒ ZKP (MPC in the head)
• DLOG + KEA3 ⇒ Three-message ZK arguments for NP (via Three-message zero-knowledge arguments)
• Quasi-polynomially hard LWE ⇒ Statistical zap arguments (via Statistical zap arguments)
• Statistically hiding COM ⇒ Statistical ZK arguments for NP (via Statistical zero-knowledge arguments)
• Zap + HSG ⇒ Non-interactive zaps (BOV) (via Non-interactive zaps)

Barriers

• No fully-black-box reduction from OWF to four-message ZK arguments (via Four-message zero-knowledge arguments) — circumvented by OWF ⇒ Four-message ZK arguments for NP
• No reduction from ZKP to Argument systems — circumvented by CRHF ⇒ Constant-round ZK argument (Barak)