The classic illustration: Peggy wants to prove to Victor she knows the secret to a cave with two passages connected by a locked door, without revealing the secret. Describe the protocol and identify which ZK property each step satisfies.
Think about your answer, then reveal below.
Model answer: Peggy enters the cave while Victor waits outside. She randomly takes passage A or B. Victor calls out which passage she must exit from. If Peggy knows the secret (can unlock the connecting door), she always exits the correct passage — completeness. If she doesn't know the secret and guessed wrong, she's caught — each round she cheats with probability 1/2, so after k rounds the chance of undetected cheating is 2^{-k} — soundness. Victor learns nothing about the secret because each round looks the same whether Peggy used the door or happened to be on the correct side — a simulator who randomly picks the correct side half the time produces an identical distribution — zero-knowledge.
This physical analogy captures the essential structure: the verifier's challenge forces the prover to demonstrate knowledge, repetition drives cheating probability to negligible, and the protocol's symmetry ensures no information leaks. Real ZK proofs replace physical caves with mathematical commitments and challenges.
Question 2 Multiple Choice
What does the simulation paradigm mean in the context of zero-knowledge, and why is it the right formalization of 'learns nothing'?
AThe verifier can simulate the prover's computation on their own hardware
BA polynomial-time simulator, given only the statement (not the witness), can produce transcripts that are computationally indistinguishable from real prover-verifier interactions. This means whatever the verifier could compute from the real interaction, they could also compute without the interaction — so the interaction provides no additional information
CThe simulation shows that the proof can be replayed by any third party
DThe simulator proves the statement is false to demonstrate no information was leaked
The simulation paradigm is the precise formalization of 'no information leaks.' If a simulator (without the witness) can produce fake transcripts indistinguishable from real ones, then the real transcript carries no computational information beyond what is already implied by the statement being true. The verifier could generate equivalent transcripts themselves without ever talking to the prover. This definition is non-trivial: it must hold even for malicious verifiers who deviate from the protocol.
Question 3 True / False
Every language in NP has a computational zero-knowledge proof, assuming one-way functions exist.
TTrue
FFalse
Answer: True
This landmark result (Goldreich, Micali, Wigderson, 1987) uses graph 3-coloring (an NP-complete problem) as the base case. They constructed a ZK proof for 3-coloring using commitment schemes (which exist if OWFs exist). Since every NP language reduces to 3-coloring, the ZK proof composes with the reduction to give ZK proofs for all of NP. This theorem means that any statement with an efficiently checkable witness can be proven without revealing the witness — a profound conceptual result.
Question 4 Multiple Choice
A zk-SNARK (Succinct Non-interactive ARgument of Knowledge) provides a zero-knowledge proof that is constant-size and verifiable in milliseconds, regardless of the complexity of the statement being proved. What is the main tradeoff?
Azk-SNARKs require quantum computers for proof generation
Bzk-SNARKs are ARguments, not proofs: soundness holds only against computationally bounded provers (not information-theoretically). Most zk-SNARKs also require a trusted setup — a one-time ceremony that generates common parameters. If the setup is compromised, fake proofs can be generated. Some newer constructions (STARKs) eliminate the trusted setup but produce larger proofs
Czk-SNARKs cannot prove statements about encrypted data
Dzk-SNARKs are only zero-knowledge in the random oracle model, not under standard assumptions
The succinct proof size and fast verification come at the cost of computational soundness (an unbounded prover could forge proofs) and, typically, a trusted setup. The trusted setup generates a structured reference string; anyone who knows the randomness used in the setup can forge proofs. Techniques like multi-party computation for the setup ceremony and transparent constructions (STARKs, Bulletproofs) mitigate this, but with efficiency tradeoffs. Zcash uses zk-SNARKs to prove transaction validity without revealing sender, receiver, or amount.
Question 5 Short Answer
A zero-knowledge proof of knowledge differs from a zero-knowledge proof of membership. What additional guarantee does it provide?
Think about your answer, then reveal below.
Model answer: A ZK proof of membership proves that a statement x is in a language L (e.g., 'this graph is 3-colorable'). A ZK proof of knowledge additionally proves that the prover actually possesses a witness w for x — not just that one exists. This is formalized by an extractor: a polynomial-time algorithm that, given the ability to rewind the prover, can extract the witness from any convincing prover. This is crucial for authentication (proving you know a password) and blockchain applications (proving you know the secret key authorizing a transaction).
The distinction matters: knowing that a graph is 3-colorable (perhaps because someone told you) is different from knowing a specific 3-coloring. Proofs of knowledge ensure the prover has constructive access to the secret, which is the relevant guarantee for cryptographic applications where the witness is a key, password, or authorization credential.