Difficulty: Advanced | Prerequisites: Basic probability (Bayes' theorem), graph theory (isomorphism), polynomial algebra, modular arithmetic. The first study notes doc on MPC and secret sharing is recommended reading before this one.
This material covers two ideas that close out EECS 376's cryptography and complexity unit. Zero-knowledge proofs ask whether a prover can convince a verifier of a statement's truth without leaking any information beyond the statement itself. The graph isomorphism setting is the canonical classroom example. Alongside this, the Lagrange interpolation problem demonstrates the mechanical side of secret recovery in Shamir's scheme: given enough shares, you reconstruct the polynomial and read off the secret. Together, these two topics tie the theoretical (what can be proved without revealing?) to the computational (how do you actually recover the secret from shares?).
A zero-knowledge proof lets a prover convince a verifier that two graphs are isomorphic (or not) without revealing the mapping itself. The graph isomorphism protocol uses random permutations and Bayes' theorem to show that a cheating prover succeeds with probability at most 1/2ᵏ over k rounds. Separately, Lagrange interpolation is the standard tool for recovering a secret from Shamir shares: build the basis polynomials, combine, and evaluate at zero.
Zero-knowledge proof (ZKP)
An interactive protocol between a prover and a verifier in which the prover convinces the verifier that a statement is true, while the verifier learns nothing beyond the truth of the statement.
Think of it as proving you know a secret without ever showing the secret itself.
Graph isomorphism
Two graphs G₁ and G₂ are isomorphic (G₁ ≅ G₂) if there exists a bijection between their vertex sets that preserves all edges. In other words, one graph is just a relabelling of the other.
In simple terms, two graphs are isomorphic if they have the same shape, just with different vertex names.
Arthur-Merlin protocol
An interactive proof system where Arthur (the verifier) uses public randomness and Merlin (the prover) tries to convince Arthur of a claim. Arthur's coin flips are visible to both parties.
Think of it as a courtroom where the judge flips coins in the open and the witness tries to build a convincing case.
Soundness
The probability that a cheating prover convinces the verifier of a false statement. A protocol with k rounds where each round has soundness error at most 1/2 achieves overall soundness error at most (1/2)ᵏ.
In simple terms, soundness measures how hard it is to cheat. More rounds make cheating exponentially harder.
Lagrange basis polynomial
The polynomial Lⱼ(x) that equals 1 at the point xⱼ and 0 at every other sample point. The set of all Lⱼ forms a basis for reconstructing any polynomial through the given points.
Think of it as a custom-built filter that picks out exactly one data point and ignores the rest.
Arthur holds two graphs G₁ and G₂. He picks i ∈ {1, 2} uniformly at random and sends Merlin a random permutation H of Gᵢ. Merlin must guess which graph H came from.
Let A be the set of all vertex renamings of G₁. Since G₁ ≅ G₂, both G₁ and G₂ belong to A. Let y = |A|.
For any particular graph H₀ in A, Pr[H = H₀ | i = 1] = 1/y = Pr[H = H₀ | i = 2]. The permutation looks the same regardless of which graph was chosen.
By Bayes' theorem: Pr[i = 1 | H = H₀] = Pr[i = 1] = 1/2. Knowing H gives Merlin no information about i.
Merlin is reduced to guessing a fair coin. Per round, Arthur accepts a wrong guess with probability ≤ 1/2.
Each round is independent.
The probability that Merlin guesses correctly in every round is at most (1/2)ᵏ.
With k rounds, Arthur rejects a cheating Merlin with probability at least 1 − 1/2ᵏ.
Arthur (the verifier) can simulate the entire interaction on his own: pick i, generate H, note Merlin's guess. Nothing in the transcript helps Arthur learn anything he could not compute alone. The proof is zero-knowledge because the verifier's view is simulatable.
Four shares are given: (1, 21), (2, 23), (3, 22), (4, 23). The goal is to recover the secret f(0) using Lagrange interpolation over ℤ₂₉ (working mod 29).
For each share point xⱼ, construct Lⱼ(x) as the product of (x − xₘ)/(xⱼ − xₘ) for all m ≠ j. The division is modular inversion mod 29.
L₁(x): denominator = (1−2)(1−3)(1−4) = −6. So L₁(x) = (x−2)(x−3)(x−4) / (−6). Modular inverse of −6 mod 29 is −5 (equivalently 24), giving (−5)(x−2)(x−3)(x−4).
L₂(x): denominator = (2−1)(2−3)(2−4) = 2. Inverse of 2 mod 29 is 15, giving (15)(x−1)(x−3)(x−4).
L₃(x): denominator = (3−1)(3−2)(3−4) = −2. Inverse of −2 mod 29 is −15 (equivalently 14), giving (−15)(x−1)(x−2)(x−4).
L₄(x): denominator = (4−1)(4−2)(4−3) = 6. Inverse of 6 mod 29 is 5, giving (5)(x−1)(x−2)(x−3).
f(x) = 21·L₁(x) + 23·L₂(x) + 22·L₃(x) + 23·L₄(x)
Each Lⱼ(0) uses only the constant factors:
L₁(0) = (−5)(−2)(−3)(−4) = (−5)(−24) = 120 → mod 29 = 4
L₂(0) = (15)(−1)(−3)(−4) = (15)(−12) = −180 → mod 29 = −6 → 23
L₃(0) = (−15)(−1)(−2)(−4) = (−15)(8) = −120 → mod 29 = 4
L₄(0) = (5)(−1)(−2)(−3) = (5)(−6) = −30 → mod 29 = −1 → 28
f(0) = 21(4) + 23(23) + 22(4) + 23(28) mod 29 = 84 + 529 + 88 + 644 mod 29 = 1345 mod 29 = 11
The secret is 11.
Lagrange basis polynomial
L_j(x) = \prod_{\substack{m=1 \\ m \neq j}}^{k} \frac{x - x_m}{x_j - x_m}Interpolating polynomial from shares
f(x) = \sum_{j=1}^{k} y_j \, L_j(x)Soundness bound over k rounds
\Pr[\text{Arthur accepts cheating Merlin}] \leq \left(\frac{1}{2}\right)^k = \frac{1}{2^k}Bayes' theorem (used in the ZKP argument)
\Pr[i=1 \mid H=H_0] = \frac{\Pr[H=H_0 \mid i=1] \cdot \Pr[i=1]}{\Pr[H=H_0]}When G₁ ≅ G₂, both conditional probabilities are 1/y, so the posterior equals the prior: 1/2.
Zero-knowledge proofs are the foundation of modern privacy-preserving authentication: proving you know a password without transmitting it, or proving a transaction is valid on a blockchain without revealing sender, recipient, or amount (as in Zcash and zk-rollups). Lagrange interpolation for secret recovery appears in distributed key management, where a quorum of servers each holding a share can reconstruct a signing key to authorise a transaction without any single server ever possessing the full key.
Students often think zero-knowledge means the verifier learns nothing at all. The verifier does learn one thing: that the statement is true. "Zero knowledge" means nothing beyond that.
A frequent error in the graph isomorphism proof is forgetting to apply Bayes' theorem. Students sometimes argue informally that "the permutation hides i" without showing that the posterior probability Pr[i = 1 | H = H₀] actually equals 1/2.
When computing Lagrange interpolation mod p, students regularly forget to use modular inverses and instead perform ordinary division. This produces wrong answers because division is not defined the same way over ℤₚ.
Students sometimes confuse the number of rounds k (which controls soundness) with the number of shares k (the threshold in Shamir's scheme). These are different parameters that happen to use the same letter in different problems.
⚠️ The Bayes' theorem step in the ZKP proof is a classic exam question. Be prepared to write out Pr[H = H₀ | i = 1], Pr[H = H₀], and show the posterior equals the prior.
⚠️ Lagrange interpolation with modular inverses is a likely computation problem. Practice computing inverses mod small primes (e.g. mod 29) quickly.
⚠️ Know how to state the soundness bound: (1/2)ᵏ over k independent rounds. Be ready to explain why independence matters.
⚠️ Understand the distinction between the zero-knowledge property (verifier learns nothing beyond the statement's truth) and soundness (cheating prover gets caught). These are separate guarantees that exams often ask you to disentangle.
True or false: In the graph isomorphism ZKP, if G₁ ≅ G₂, Merlin can determine which graph Arthur permuted with certainty. (False: Pr[i = 1 | H] = 1/2.)
Fill in the blank: The probability Arthur accepts a cheating Merlin over k rounds is at most ______. (1/2ᵏ)
True or false: To compute L₂(0) mod 29, you can simply divide by the denominator using normal division. (False: you must use the modular multiplicative inverse.)
Fill in the blank: In the worked example, f(0) mod 29 = ______. (11)
True or false: Zero-knowledge and soundness are the same property viewed from different sides. (False: zero-knowledge protects the prover's information; soundness protects the verifier from being fooled.)
Q: In the graph isomorphism ZKP, prove that Pr[i = 1 | H = H₀] = 1/2 when G₁ ≅ G₂.
A: Let A be the set of all vertex renamings of G₁. Since G₁ ≅ G₂, both belong to A, so |A| = y. For any H₀ in A, Pr[H = H₀ | i = 1] = 1/y = Pr[H = H₀ | i = 2]. Then Pr[H = H₀] = (1/2)(1/y) + (1/2)(1/y) = 1/y. By Bayes' theorem, Pr[i = 1 | H = H₀] = (1/y)(1/2) / (1/y) = 1/2.
Q: Using Lagrange interpolation over ℤ₂₉, recover the secret from shares (1, 21), (2, 23), (3, 22), (4, 23).
A: Build L₁ through L₄, compute their values at x = 0: L₁(0) = 4, L₂(0) ≡ −6 mod 29 = 23, L₃(0) = 4, L₄(0) ≡ −1 mod 29 = 28. Then f(0) = 21(4) + 23(23) + 22(4) + 23(28) = 1345 ≡ 11 mod 29. The secret is 11.
Q: Why does repeating the ZKP protocol for k rounds reduce the cheating probability to (1/2)ᵏ?
A: Each round is an independent trial where Merlin must guess a uniformly random bit. His probability of guessing correctly in any single round is at most 1/2. Since Arthur requires correct guesses in all k rounds, the probability of success is at most (1/2)ᵏ by independence.
Q: What is the difference between zero-knowledge and soundness?
A: Zero-knowledge ensures the verifier learns nothing beyond the truth of the statement (the verifier's view is simulatable). Soundness ensures a cheating prover cannot convince the verifier of a false statement (the probability of fooling the verifier is bounded). They protect different parties: zero-knowledge protects the prover, soundness protects the verifier.
The zero-knowledge proof for graph isomorphism connects to the broader theory of interactive proofs and the complexity class IP (which equals PSPACE). The Arthur-Merlin framework extends to probabilistically checkable proofs (PCPs), a cornerstone of hardness-of-approximation results. Lagrange interpolation ties back directly to the secret sharing material in the companion study notes: the uniqueness proof there is what guarantees that this interpolation step always produces the correct answer.
Zero-knowledge proof, ZKP, interactive proof, Arthur-Merlin protocol, graph isomorphism, vertex renaming, permutation, Bayes' theorem, soundness, completeness, zero-knowledge property, simulatability, Lagrange interpolation, Lagrange basis polynomial, modular inverse, secret recovery, Shamir's secret sharing, polynomial reconstruction, ℤₚ, prime field, EECS 376, foundations of computer science, University of Michigan