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 efficient (or unbounded, for statistical soundness) $P^{\ast }$: $\mathrm{Pr}[V\text{ accepts in }⟨P^{\ast }(x),V(x)⟩]\le \mathrm{negl}(\lambda ).$

A proof system with computationally sound soundness is called 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.

Argument systems

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

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
• ZKP ⇒ Auxiliary-input OWF
• Sequential composition of ZK proofs preserves ZK; parallel composition may not — GK96a
• HVZK ⇒ NIZK (Fiat–Shamir)

Participates in

Builds on Zero-knowledge proof

• HVZK ⇒ NIZK (Fiat–Shamir) (via Honest-verifier ZK (HVZK))
• ZKP ⇒ Auxiliary-input OWF

Produces Zero-knowledge proof

• CRHF ⇒ Constant-round ZK argument (Barak) (via Argument systems)
• OWF ⇒ ZKP

Barriers

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