47.06.03 · theoretical-cs / 06-cryptographic-foundations

Zero-Knowledge Proofs: Interactive Protocols and Proof Systems

shipped3 tiersLean: none

Anchor (Master): Arora and Barak 2009 Computational Complexity: A Modern Approach (Cambridge) Ch. 8; Goldreich, Micali and Wigderson 1991 Proofs that Yield Nothing But Their Validity (JACM); Blum, Feldman and Micali 1988 Non-Interactive Zero-Knowledge and Its Applications (FOCS)

Intuition Beginner

You want to prove to a friend that you solved a Sudoku puzzle without revealing the solution. Zero-knowledge proofs make this possible. You convince the verifier that a statement is true while revealing nothing beyond its truth.

The classic example is the cave. Imagine a circular cave with a magic door in the middle that requires a secret password to open. You want to prove you know the password without revealing it. Your friend stands outside the cave and watches you enter from one side. They then shout "come out the left!" or "come out the right!" at random. If you know the password, you can always comply (opening the door if needed). If you do not know it, you can only comply half the time (when they ask for the side you entered from). Repeating this 20 times, the probability of fooling your friend drops to less than one in a million.

A zero-knowledge proof has three properties. Completeness: an honest prover with a valid proof convinces an honest verifier. Soundness: a cheating prover cannot convince the verifier of a false statement. Zero-knowledge: the verifier learns nothing beyond the truth of the statement, because everything they saw could have been simulated without the prover.

The deep result is that every NP statement has a zero-knowledge proof. You can prove you know a 3-colouring of a graph, a satisfying assignment for a formula, or a Hamiltonian cycle, without revealing any information about the witness.

Visual Beginner

Zero-knowledge proof for Graph 3-Colouring:

  Prover has: valid 3-colouring (R, G, B) of the graph
  Verifier sees: the graph (but not the colouring)

  Round i:
    1. Prover: randomly permute colours (R->B, G->R, B->G)
    2. Prover: commit to each vertex's permuted colour
    3. Verifier: pick a random edge (u, v)
    4. Prover: open commitments for u and v
    5. Verifier: check u and v have different colours

  If graph IS 3-colourable: prover always passes (colours differ)
  If graph is NOT 3-colourable: >= 1 edge has same colour
    Verifier catches this with prob >= 1/|E| per round

Property	Meaning	How it holds
Completeness	True statement: honest prover convinces verifier	Valid 3-colouring means every edge has different colours
Soundness	False statement: cheating prover caught with high prob	Invalid colouring has at least one bad edge, verifier finds it
Zero-knowledge	Verifier learns nothing beyond validity	Simulator picks random edge first, colours only that edge correctly

Worked example Beginner

We do a zero-knowledge proof that the graph $K_{3}$ (triangle with vertices $a, b, c$ ) is 3-colourable. The actual colouring is: $a = R, b = G, c = B$ .

Round 1. Prover picks permutation $π$ : swap R and G, keep B. New colours: $a = G, b = R, c = B$ . Prover commits to each: $com (a, G), com (b, R), com (c, B)$ . Sends commitments to verifier.

Verifier picks edge $(a, c)$ . Prover opens $com (a, G)$ and $com (c, B)$ . Verifier checks: $G \neq = B$ . Pass.

Round 2. Prover picks new permutation $π^{'}$ : rotate $(R, G, B) \to (B, R, G)$ . New colours: $a = B, b = R, c = G$ . Commits and sends.

Verifier picks edge $(b, a)$ . Prover opens: $b = R, a = B$ . Verifier checks: $R \neq = B$ . Pass.

After many rounds, the verifier is convinced. But the verifier never sees the original colouring, only random permutations of it. Each opened pair is consistent with many possible colourings, so no information about the original is revealed.

Check your understanding Beginner

Formal definition Intermediate+

Definition (interactive proof system). An interactive proof system for a language $L$ is a pair $(P, V)$ where $P$ is computationally unbounded and $V$ is PPT, satisfying:

(Completeness) For every $x \in L$ : $Pr [⟨ P, V ⟩ (x) = 1] = 1$ .
(Soundness) For every $x \in / L$ and every $P^{*}$ : $Pr [⟨ P^{*}, V ⟩ (x) = 1] \leq 1/3$ .

Definition (computational zero-knowledge). An interactive proof $(P, V)$ for $L$ is computational zero-knowledge if there exists a PPT simulator $S$ such that for every PPT $V^{*}$ , the following distributions are computationally indistinguishable:

{View_{V^{*}} (⟨ P, V^{*} ⟩ (x))}_{x \in L} \approx_{c} {S (x, V^{*})}_{x \in L} .

Definition (commitment scheme). A commitment scheme is a pair $(C o mmi t, O p e n)$ where $C o mmi t (m, r)$ produces a commitment $c$ to message $m$ using randomness $r$ , satisfying:

(Binding) It is computationally infeasible to find $(m_{1}, r_{1}, m_{2}, r_{2})$ with $m_{1} \neq = m_{2}$ and $C o mmi t (m_{1}, r_{1}) = C o mmi t (m_{2}, r_{2})$ .
(Hiding) $C o mmi t (m_{1}, r_{1})$ and $C o mmi t (m_{2}, r_{2})$ are computationally indistinguishable for any $m_{1}, m_{2}$ .

Counterexamples to common slips

"Zero-knowledge means the proof reveals no information." The proof reveals that the statement is true. Zero-knowledge means the proof reveals nothing beyond the truth of the statement. The distinction matters.
"Any interactive proof is zero-knowledge." No. A standard interactive proof may leak information about the witness. Zero-knowledge is an additional property requiring the existence of a simulator.
"Zero-knowledge proofs are always non-interactive." The basic definition is interactive. Non-interactive zero-knowledge (NIZK) is a special case requiring a common reference string. The Fiat-Shamir heuristic converts some interactive ZK proofs to non-interactive ones in the random oracle model.

Key theorem with proof Intermediate+

Theorem (GMW: every NP language has a ZK proof). Assuming one-way functions exist, every language in NP has a computational zero-knowledge proof system.

Proof sketch. By NP-completeness, it suffices to give a ZK proof for Graph 3-Colouring (3COL). The reduction from any NP language to 3COL is polynomial-time.

Protocol. Let $G = (V, E)$ be a graph and $φ : V \to {1, 2, 3}$ a valid 3-colouring (the witness). Repeat $∣ E ∣^{2}$ times:

Prover picks a random permutation $π$ of ${1, 2, 3}$ and commits to $π (φ (v))$ for each $v \in V$ .
Verifier picks a random edge $(u, v) \in E$ .
Prover opens the commitments for $u$ and $v$ .
Verifier checks $π (φ (u)) \neq = π (φ (v))$ .

Completeness. If $φ$ is valid, $φ (u) \neq = φ (v)$ for every edge, so $π (φ (u)) \neq = π (φ (v))$ . The verifier always accepts.

Soundness. If $G$ is not 3-colourable, every colouring has at least one edge with the same colour on both endpoints. The verifier finds this edge with probability at least $1/∣ E ∣$ per round. Over $∣ E ∣^{2}$ rounds, the probability the cheating prover escapes is at most $(1 - 1/∣ E ∣)^{∣ E ∣^{2}} \leq e^{- ∣ E ∣}$ , which is negligible.

Zero-knowledge. The simulator $S$ for a single round works as follows: pick a random edge $(u^{*}, v^{*})$ and a random pair of distinct colours $c_{u}, c_{v}$ . Commit to $c_{u}$ for $u^{*}$ , $c_{v}$ for $v^{*}$ , and random values for all other vertices. Run the verifier $V^{*}$ to get its query edge $(u, v)$ . If $(u, v) = (u^{*}, v^{*})$ , output the transcript. Otherwise, rewind and try again.

The simulator succeeds with probability $1/∣ E ∣$ per attempt, so the expected number of attempts is $∣ E ∣$ . The output distribution is identical to the real interaction because: (1) the permutation is random in both, (2) the opened colours are a random pair of distinct colours in both, and (3) the unopened commitments are computationally hiding in both.

The commitment scheme exists if one-way functions exist (by Naor's theorem, 1991). $□$

Bridge. The GMW theorem is the foundational reason zero-knowledge is universal for NP: by reducing any NP statement to 3-colouring and applying the commitment-based protocol, every claim of the form "I know a witness for $x \in L$ " can be proven without revealing the witness. This builds toward the broader theory of cryptographic protocols where ZK proofs are composed into secure multiparty computation, and this is exactly the pattern that appears again in 47.06.04 where the Fiat-Shamir heuristic converts interactive ZK protocols into digital signatures. The central insight is that commitment schemes (which exist iff OWFs exist) provide the hiding and binding properties that make zero-knowledge possible, and putting these together with the interactive proof framework of 47.03.04 shows that ZK proofs add a privacy layer on top of the IP framework: IP = PSPACE captures what can be proved, while ZK captures what can be proved privately.

Exercises Intermediate+

Exercise 3 (medium, symbolic).

Construct a zero-knowledge proof for Graph Isomorphism: given two graphs $G_{1}$ and $G_{2}$ , prove they are isomorphic without revealing the isomorphism.

Answer

Protocol. Prover knows isomorphism $σ$ with $G_{2} = σ (G_{1})$ .

Prover picks a random permutation $π$ and computes $H = π (G_{1})$ . Sends $H$ .
Verifier sends a random challenge $i \in {1, 2}$ .
If $i = 1$ : prover sends $π$ . Verifier checks $H = π (G_{1})$ .
If $i = 2$ : prover sends $π \circ σ^{- 1}$ . Verifier checks $H = (π \circ σ^{- 1}) (G_{2})$ .

Completeness: If $G_{1} ≅ G_{2}$ , the prover can answer both challenges correctly.

Soundness: If $G_{1} \neq ≅ G_{2}$ , no $H$ can be isomorphic to both. So the prover can prepare for at most one challenge, and fails with probability $1/2$ per round.

Zero-knowledge: Simulator picks random $i^{*}$ and $ψ$ , computes $H = ψ (G_{i^{*}})$ . If the verifier challenges $i = i^{*}$ , output the transcript. Otherwise, rewind. The output is identical to the real protocol.

Exercise 4 (medium, short answer).

Explain the difference between honest-verifier zero-knowledge (HVZK) and general zero-knowledge. Why does the GMW protocol achieve general ZK?

Answer

HVZK means the simulator only needs to simulate the view of the honest verifier $V$ (who follows the protocol). General ZK requires simulation for any PPT verifier $V^{*}$ (who may deviate arbitrarily). The GMW protocol achieves general ZK because the simulator rewinds $V^{*}$ : it runs $V^{*}$ to get its challenge, and if the challenge does not match the simulator's prepared response, it rewinds $V^{*}$ to the beginning of the round and tries again. This works because the commitment scheme hides the prepared response from $V^{*}$ , so $V^{*}$ 's challenge is independent of the simulator's trapdoor. The expected number of rewinding attempts is polynomial.

Exercise 5 (medium, symbolic).

The Fiat-Shamir heuristic converts an interactive ZK protocol into a non-interactive one by replacing the verifier's challenge with a hash of the prover's first message. Show that if the hash function is modelled as a random oracle, this produces a secure NIZK.

Answer

In the random oracle model, the hash function $H$ is a truly random function. The prover computes $H$ on their commitment message to get the challenge. Since $H$ is random, the challenge is uniformly distributed and independent of the commitment (from the prover's perspective, it is as if the verifier sent a random challenge).

Soundness in the random oracle model: a cheating prover must either (1) predict the output of $H$ on their commitment (impossible since $H$ is random), or (2) find two commitments that hash to challenges for which they can answer both (the "forking lemma" bounds this probability).

Zero-knowledge: the simulator programs the random oracle. It picks the challenge first, computes a commitment consistent with that challenge, and sets $H (commitment) = challenge$ . The resulting transcript is identical to a real execution, and the random oracle programming is undetectable because the simulator's commitment has the same distribution as the real one.

Exercise 6 (hard, symbolic).

Prove that commitment schemes exist if and only if one-way functions exist. (One direction: OWF implies commitment. For the other, show that a commitment scheme yields a OWF.)

Answer

OWF implies commitment (Naor 1991). Given a PRG $G : {0, 1}^{n} \to {0, 1}^{3 n}$ (from any OWF via HILL), define: to commit to bit 0, send $G (s)$ for random $s$ ; to commit to bit 1, send $G (s) \oplus r$ for random $r$ chosen by the receiver. Hiding follows from the PRG property (both $G (s)$ and $G (s) \oplus r$ look random). Binding follows from the fact that finding $s_{0}, s_{1}$ with $G (s_{0}) = G (s_{1}) \oplus r$ would break the PRG.

Commitment implies OWF. Given a commitment scheme $(C o mmi t, O p e n)$ , define $f (m, r) = C o mmi t (m, r)$ . This is polynomial-time computable. To invert: given $c$ , find $(m, r)$ with $C o mmi t (m, r) = c$ . By the binding property, there is at most one valid opening (computationally), so inversion requires finding the committed message. If $f$ were easy to invert, the hiding property would be violated (an inverter could recover $m$ from $c$ , distinguishing commitments to different messages). More formally, if $A$ inverts $f$ with probability $ε$ , then $A (C o mmi t (m, r))$ returns some $(m^{'}, r^{'})$ with $C o mmi t (m^{'}, r^{'}) = C o mmi t (m, r)$ . By binding, $m^{'} = m$ with high probability, so $A$ recovers $m$ from the commitment, violating hiding. Rubric: full credit for both directions.

Exercise 7 (hard, symbolic).

A Sigma protocol is a 3-round interactive proof $(co mmi t, c ha l l e n g e, r es p o n se)$ with special honest-verifier zero-knowledge (SHVZK) and special soundness. Prove that any Sigma protocol can be compiled into a signature scheme using the Fiat-Shamir transform.

Answer

Let $(P, V)$ be a Sigma protocol for relation $R$ with special soundness (given two accepting transcripts with the same commitment but different challenges, the witness can be extracted) and SHVZK (simulator produces valid transcript given just the challenge).

Signature scheme. Key generation: pick $(p k, s k) = (x, w)$ where $(x, w) \in R$ . Sign message $m$ : compute commitment $a = P_{1} (w, x)$ , challenge $c = H (a, m)$ , response $z = P_{2} (w, x, a, c)$ . Signature is $(a, c, z)$ .

Verify: check $V (x, a, c, z) = 1$ and $c = H (a, m)$ .

Unforgeability (sketch). By the forking lemma: if a forger produces a valid signature $(a, c, z)$ on a new message $m$ , rewind the forger with a different random oracle response $c^{'} \neq = c$ to the query $H (a, m)$ . With probability $ε / q_{H}$ (where $q_{H}$ is the number of hash queries), the forger produces $(a, c^{'}, z^{'})$ also valid. By special soundness, the two transcripts $(a, c, z)$ and $(a, c^{'}, z^{'})$ allow extraction of the witness $w$ , breaking the hardness of $R$ .

Zero-knowledge property of signatures. The Fiat-Shamir transform produces a "proof of knowledge" in the random oracle model: anyone can verify the signature, but the signature reveals nothing about $w$ beyond knowledge of it, because the simulator can program $H$ to produce valid signatures without $w$ . Rubric: full credit for the forking lemma argument and the extraction.

Exercise 8 (hard, short answer).

Explain why perfect zero-knowledge for all of NP would imply that the polynomial hierarchy collapses. What does this say about the relationship between statistical and computational ZK?

Answer

If every NP language had a perfect zero-knowledge proof (PZK), then the PZK class would contain all of NP. But it is known that PZK is contained in AM (the Arthur-Merlin class), and if NP is contained in AM, then the polynomial hierarchy collapses to its second level (PH = AM). This is because Boppora, Feldman and Fortnow showed that PZK is contained in SZE (statistical zero-knowledge), which is contained in AM.

In practice, the GMW protocol achieves computational zero-knowledge (CZK) for all of NP, not perfect. The gap between statistical and computational ZK is the same as the gap between information-theoretic and computational security: statistical ZK provides stronger guarantees but is more limited in scope (SZK does not contain all of NP unless PH collapses), while computational ZK relies on hardness assumptions but achieves universality.

Lean formalization Intermediate+

Mathlib has no formalization of zero-knowledge proofs, interactive proof systems, commitment schemes, or simulators. A formalization would require an InteractiveProtocol typeclass with prover and verifier as probabilistic computations, a ZeroKnowledge predicate requiring the existence of a simulator, and a computational indistinguishability relation on distributions of transcripts. The foundational gap is the absence of any ProbabilisticComputation monad in Mathlib's type theory. This unit ships without a lean_module.

Advanced results Master

Three directions extend the ZK framework.

Result 1 (NIZK and the common reference string). Blum, Feldman and Micali (1988) introduced non-interactive zero-knowledge proofs in the common reference string (CRS) model. The prover sends a single message, and the verifier checks it using a publicly known CRS. The CRS is generated by a trusted setup. Feige, Lapidot and Shamir (1990) showed that every NP language has a NIZK in the CRS model assuming one-way functions. NIZKs are essential for efficient cryptographic protocols because they eliminate the interaction rounds ^{[Arora-Barak Ch. 8]}.

Result 2 (zk-SNARKs). Succinct Non-interactive ARguments of Knowledge (SNARKs) are NIZKs with sublinear proof size and sublinear verification time. The construction of Bitansky, Canetti, Chiesa and Tromer (2012) uses arithmetic circuit satisfiability and elliptic curve pairings. A zk-SNARK for an NP statement of size $n$ has proof size $O (1)$ group elements and verification time $O (1)$ pairings plus input processing. zk-SNARKs are used in blockchain systems (Zcash, Ethereum) for privacy-preserving transactions ^{[Arora-Barak Ch. 8]}.

Result 3 (ZK and secure multiparty computation). The GMW theorem extends beyond proofs to computation: Goldreich, Micali and Wigderson (1987) proved that any polynomial-time function can be computed by $n$ parties such that each party learns only the output and nothing about other parties' inputs. The construction uses ZK proofs as a subroutine to enforce honest behaviour. This is the foundational result of secure multiparty computation (MPC), with applications to privacy-preserving machine learning, threshold cryptography, and distributed voting ^{[Arora-Barak Ch. 8]}.

Synthesis. Zero-knowledge proofs are the foundational reason privacy and verification can coexist: the simulator paradigm ensures that interaction reveals nothing beyond the statement's truth, and this builds toward the entire field of privacy-preserving cryptography where ZK proofs compose into MPC, NIZK, and SNARKs. The central insight is that the three properties (completeness, soundness, zero-knowledge) are not in tension: the same commitment scheme that enables soundness (binding) also enables zero-knowledge (hiding), and this is exactly the pattern that appears again in 47.06.01 where one-way functions provide both pseudorandomness and one-wayness. Putting these together with the interactive proof theory of 47.03.04 shows that ZK proofs are interactive proofs refined with a privacy guarantee, and the fact that every NP statement has a ZK proof means that privacy is free: any proof can be made zero-knowledge without changing what can be proved, only how it is proved.

Full proof set Master

Proposition 1 (GMW protocol for 3COL is zero-knowledge). The GMW protocol for Graph 3-Colouring is computational zero-knowledge assuming computationally hiding commitments.

Proof. We construct a simulator $S$ for a single round. $S$ receives $G = (V, E)$ and has black-box access to verifier $V^{*}$ .

$S$ picks a random edge $(u^{*}, v^{*}) \in E$ and random distinct colours $c_{u^{*}}, c_{v^{*}} \in {1, 2, 3}$ . For all other vertices $w \in / {u^{*}, v^{*}}$ , $S$ commits to a random colour. $S$ sends all commitments to $V^{*}$ and receives its challenge edge $(u, v)$ .

If $(u, v) = (u^{*}, v^{*})$ , $S$ opens the commitments for $u$ and $v$ (revealing $c_{u^{*}}, c_{v^{*}}$ ) and outputs the transcript. If $(u, v) \neq = (u^{*}, v^{*})$ , $S$ rewinds $V^{*}$ to the beginning and tries again.

Success probability. Each attempt succeeds with probability at least $1/∣ E ∣$ (the probability $V^{*}$ picks the edge $S$ prepared). Expected number of attempts: $∣ E ∣$ .

Indistinguishability. The real transcript has: commitments to $π (φ (v))$ for random $π$ , opened colours $π (φ (u)), π (φ (v))$ for the queried edge. The simulated transcript has: commitments to random values (except the prepared edge), opened colours $c_{u^{*}}, c_{v^{*}}$ (random distinct pair). By the hiding property of commitments, the unopened commitments are indistinguishable in both distributions. The opened colours are uniformly random distinct pairs in both. So the full transcripts are computationally indistinguishable. $□$

Proposition 2 (composition of ZK proofs). If $(P_{1}, V_{1})$ is a ZK proof for $L_{1}$ and $(P_{2}, V_{2})$ is a ZK proof for $L_{2}$ , then the parallel composition (run both protocols simultaneously) is a ZK proof for $L_{1} \land L_{2}$ .

Proof. The composed simulator $S$ runs $S_{1}$ and $S_{2}$ independently to simulate the transcripts for both protocols. Since $S_{1}$ 's output is indistinguishable from the real $P_{1}$ - $V_{1}^{*}$ interaction, and $S_{2}$ 's output is indistinguishable from the real $P_{2}$ - $V_{2}^{*}$ interaction, the joint output is indistinguishable from the real joint interaction by the hybrid argument (replace one protocol's transcript at a time). $□$

Connections Master

47.06.01 — One-way functions provide the commitment schemes needed for ZK proofs; the GMW theorem that every NP language has a ZK proof is conditional on OWF existence.
47.03.04 — IP = PSPACE establishes the power of interactive proofs; ZK proofs add the zero-knowledge property, showing that privacy is compatible with the full power of IP.
47.06.02 — The discrete logarithm setting provides the algebraic structure for Schnorr protocols, which are efficient Sigma protocols (a subclass of ZK proofs).
47.06.04 — Digital signatures can be derived from ZK proofs via the Fiat-Shamir heuristic, converting interactive ZK into non-interactive authentication.

Historical & philosophical context Master

Zero-knowledge proofs were introduced by Goldwasser, Micali and Rackoff (1985) in their paper "The Knowledge Complexity of Interactive Proof Systems." The concept was initially met with scepticism—the idea that one could prove knowledge without revealing it seemed paradoxical. The GMW theorem (1986, published 1991) established that ZK proofs exist for all of NP, transforming the concept from a curiosity into a fundamental tool.

The philosophical significance is that knowledge and privacy are not in conflict. Any proof can be restructured to reveal nothing beyond its conclusion. This has profound implications: in principle, every authentication, verification, and audit process can be performed without exposing private data. The gap between principle and practice is engineering, not theory ^{[Arora-Barak Ch. 8]}.

The development of zk-SNARKs (2012-2013) brought ZK proofs into practical use. Zcash (2016) was the first large-scale deployment, using zk-SNARKs to prove transaction validity without revealing sender, receiver, or amount. The technology has since spread to Ethereum, where zk-rollups use SNARKs for scalability and privacy.

Bibliography Master

@book{arora2009computational,
  author    = {Arora, Sanjeev and Barak, Boaz},
  title     = {Computational Complexity: A Modern Approach},
  publisher = {Cambridge University Press},
  year      = {2009},
}
@article{goldwasser1989knowledge,
  author  = {Goldwasser, Shafi and Micali, Silvio and Rackoff, Charles},
  title   = {The Knowledge Complexity of Interactive Proof Systems},
  journal = {SIAM Journal on Computing},
  volume  = {18},
  number  = {1},
  pages   = {186--208},
  year    = {1989},
}
@article{goldreich1991proofs,
  author  = {Goldreich, Oded and Micali, Silvio and Wigderson, Avi},
  title   = {Proofs that Yield Nothing But Their Validity or All Languages in {NP} Have Zero-Knowledge Proof Systems},
  journal = {Journal of the ACM},
  volume  = {38},
  number  = {3},
  pages   = {691--729},
  year    = {1991},
}
@inproceedings{blum1988noninteractive,
  author    = {Blum, Manuel and Feldman, Paul and Micali, Silvio},
  title     = {Non-Interactive Zero-Knowledge and Its Applications},
  booktitle = {Proceedings of the 20th ACM Symposium on Theory of Computing},
  year      = {1988},
  pages     = {103--112},
}

Prerequisites

47.06.01

Tier anchors

beginner: Arora and Barak 2009 Computational Complexity: A Modern Approach (Cambridge) Ch. 8 (proving you know something without revealing what you know)
intermediate: Arora and Barak 2009 Computational Complexity: A Modern Approach (Cambridge) Ch. 8 (formal ZK definition, Graph 3-Colouring protocol, Sigma protocols, simulator-based security)
master: Arora and Barak 2009 Computational Complexity: A Modern Approach (Cambridge) Ch. 8; Goldreich, Micali and Wigderson 1991 Proofs that Yield Nothing But Their Validity (JACM); Blum, Feldman and Micali 1988 Non-Interactive Zero-Knowledge and Its Applications (FOCS)

References

Arora, S. and Barak, B. — Computational Complexity: A Modern Approach · Cambridge University Press (2009). Chapter 8 develops zero-knowledge proofs, defining an interactive proof system $(P, V)$ where $P$ is an unbounded prover and $V$ is a probabilistic polynomial-time verifier satisfying completeness ( $x \in L \Rightarrow Pr [V accepts] = 1$ ) and soundness ( $x \in / L \Rightarrow Pr [V accepts] \leq 1/3$ ); a zero-knowledge proof additionally satisfies that there exists a PPT simulator $S$ such that for every PPT verifier $V^{*}$ , the view of $V^{*}$ in the interaction with $P$ is computationally indistinguishable from $S (x)$ ; the chapter presents the Goldreich-Micali-Wigderson protocol for Graph 3-Colouring (ZK proof that a graph is 3-colourable using commitments to random permutations of the colouring, verifier checks one edge), and proves that every language in NP has a zero-knowledge proof assuming one-way functions exist.
Goldreich, O., Micali, S. and Wigderson, A. — Proofs that Yield Nothing But Their Validity or All Languages in NP Have Zero-Knowledge Proof Systems · Journal of the ACM 38(3):691--729 (1991). Proves that every language in NP has a zero-knowledge proof system, assuming the existence of one-way functions; the construction reduces any NP language to 3SAT, then to Graph 3-Colouring (using the gadget reduction), and applies the GMW zero-knowledge protocol for 3-colouring; the proof that the protocol is zero-knowledge uses a simulator that guesses which edge the verifier will query and constructs a commitment consistent with that edge.

Estimated time

beginner: 15m
intermediate: 40m
master: 90m