The Graph Isomorphism Example
What you'll learn: You'll walk through the classic graph isomorphism protocol to see exactly how zero-knowledge proofs work in practice.
The Setup
Imagine you have two graphs (networks of connected dots). You claim they're isomorphic—meaning they're structurally identical, just with nodes labeled differently. You want to prove you know the mapping between them without revealing what that mapping actually is.
The Protocol Step-by-Step
Your secret: You know how to relabel Graph A to make it identical to Graph B.
The proof process:
- You (Prover): Randomly shuffle Graph A's labels to create Graph C. Send Graph C to the Verifier.
- Verifier: Randomly challenges you: "Show me C is isomorphic to either A or B."
- You respond: Since you created C from A, you can always answer either challenge:
- If asked about A: reveal the shuffling you just applied
- If asked about B: use your secret A↔B mapping plus the shuffle
- Repeat many times: One lucky guess is 50/50, but 20 correct answers means less than 1-in-a-million chance of faking it.
Why It's Zero-Knowledge
The Verifier learns nothing about your actual A↔B mapping. They only see random shuffles and single-step connections. Each round, you're essentially saying "I can connect any graph to either A or B" without exposing the direct A-to-B path.
This is an interactive proof—it requires back-and-forth challenges. The security comes from repetition: a faker can only guess correctly 50% of the time per round.
Key Takeaway: The graph isomorphism protocol demonstrates zero-knowledge proofs through repeated random challenges where correct responses prove knowledge without revealing the secret mapping itself.