On this page
Most school proofs give everything away. Show that 91 is not prime and you hand over the factors, 7 and 13. In 1985 three researchers asked a stranger question: could you convince someone a statement is true without telling them anything else?
Shafi Goldwasser, Silvio Micali and Charles Rackoff said yes, in "The Knowledge Complexity of Interactive Proof Systems", presented at the 1985 ACM Symposium on Theory of Computing (STOC '85 paper).
What is a zero-knowledge proof?
In the journal version of the paper, zero-knowledge proofs are "those proofs that convey no additional knowledge other than the correctness of the proposition in question" (SIAM Journal on Computing, 1989).
Textbook treatments describe three properties (overview):
Completeness: if the statement is true, an honest prover can convince an honest verifier.
Soundness: if the statement is false, a cheating prover gets through only with a small probability.
Zero-knowledge: the verifier learns nothing except that the statement is true.
The key move was to make the proof a conversation. As MIT News puts it, the paper used interaction (messages going back and forth) and probabilism (tossing coins to choose which messages to send) to establish a fact "via a statistical argument without providing any additional information as to why it is true."
Who are Goldwasser, Micali and Rackoff?
Goldwasser and Micali began working together in 1980 as graduate students at the University of California, Berkeley, with Manuel Blum, their thesis advisor (MIT News). On winning the Turing Award, Goldwasser said: "Our work was very unconventional at the time. We were graduate students and let our imagination run free."
The journal version of the paper shared the 1993 Gödel Prize with a paper by László Babai and Shlomo Moran; the two papers introduced interactive proof systems (ACM SIGACT). In 2013 Goldwasser and Micali received the 2012 ACM Turing Award, which carries a $250,000 prize, for their work in cryptography and complexity theory (MIT News).
How can you prove you know a secret without revealing it?
The classic explanation is a cave story from "How to Explain Zero-Knowledge Protocols to Your Children", presented at CRYPTO '89 (Quisquater and colleagues).
A ring-shaped cave splits into paths A and B, which meet at a locked door at the back. Priya says she knows the door's password. Vikram wants proof, but she will not say the word.
Vikram waits outside. Priya walks in along A or B, chosen at random.
Vikram goes to the fork and shouts which path she must come out of, also at random.
If Priya knows the password, she always comes out the right way, using the door if needed.
If she does not, she succeeds only when she already picked his path: a 1 in 2 chance.
Now repeat it. A bluffer must guess right every round, so her chance of surviving n rounds is (1/2)^n. After 10 rounds that is 1 in 1,024; after 20 rounds, 1 in 1,048,576, about one in a million (worked figure). It is the same repeated-trials reasoning as in the probability of at least one six in four rolls.
Why does Vikram learn nothing? All he sees is Priya appearing where he asked. A video would not convince anyone else, because two people could stage it without the password by agreeing on the paths in advance.
If (1/2)^n still feels slippery, the Fermi Concept Library has its own lesson for each concept in mathematics, so you can rebuild probability one idea at a time.
Does this work for real maths problems, not just caves?
Yes. In 1991 Oded Goldreich, Micali and Avi Wigderson published "Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems" (Journal of the ACM). Their example was three-colouring a network so no two linked dots match, assuming secure encryption exists (overview). Roughly, the prover reshuffles the colours, hides each dot's colour in a locked box, and lets the verifier open one link; if its two ends differ, the round passes.
Cryptography's earlier story was code-makers against code-breakers, from Al-Kindi's frequency analysis to Alan Turing's Bombe against Enigma. Goldwasser and Micali also introduced the simulation paradigm: a system is shown to be secure by proving that an attacker could have simulated everything they saw on their own. MIT News lists its uses in authentication, data integrity, software protection and many-party protocols such as electronic elections and auctions (MIT News).
Try it yourself: a 10-minute zero-knowledge game
You need a friend who cannot tell red from green, and one red and one green ball that are otherwise identical. You claim the balls differ.
Your friend holds one ball in each hand behind their back.
They secretly swap the balls or not, then show them again.
You say "swapped" or "not swapped".
Repeat 10 times. If the balls were really the same colour, you are guessing: your chance of always being right is (1/2)^10, or 1 in 1,024.
Then check the three properties:
Could an honest you always win? (completeness)
Could a bluffer win often? (soundness)
Does your friend now know which ball is red? (zero-knowledge: no)
If you get stuck working out the odds for more rounds, the Fermi Problem Library has a step-by-step solver that explains the reasoning rather than printing an answer.
