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 whose first message, a random string sent by the verifier, can be fixed once and reused for any number of statements — 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).

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.

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 — GK96b.

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
• 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
• HVZK ⇒ NIZK (Fiat–Shamir)

Participates in

Builds on Zero-knowledge proof

• HVZK ⇒ NIZK (Fiat–Shamir) (via Honest-verifier ZK (HVZK))

Produces Zero-knowledge proof

• Bilinear pairing + DLIN ⇒ Zaps (non-interactive) (via Zaps)
• 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
• iO ⇒ Statistical ZK arguments for NP (via Statistical zero-knowledge arguments)
• NIZK ⇒ Zaps (Dwork–Naor) (via Zaps)
• 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)
• Quasi-polynomially hard LWE ⇒ Statistical zap arguments (via Statistical zap arguments)
• Statistically hiding COM ⇒ Statistical ZK arguments for NP (via Statistical zero-knowledge arguments)

Barriers

• No reduction from ZKP to Argument systems — circumvented by CRHF ⇒ Constant-round ZK argument (Barak)