The encyclopedia · R&D & Science · Technical decision · 1985–1989
Zero-knowledge proofs convinced a verifier without revealing the secret
Goldwasser, Micali and Rackoff proved you can convince someone a statement is true while leaking nothing beyond that truth.
Massachusetts Institute of Technology
The solution
In 1985, Shafi Goldwasser, Silvio Micali and Charles Rackoff introduced interactive proof systems and defined their knowledge complexity. The central question: how much does a verifier learn from a proof beyond the fact that the statement is true?
The naive way to prove you know something is to reveal it — but that hands over the secret. The naive alternative, a trusted third party vouching for you, merely moves the problem. GMR proposed conversations where the prover's messages convince, yet the verifier's entire view could be reproduced by a simulator that knows no secret.
Because the simulation exists, the verifier mathematically learns nothing except the assertion's validity. The 1985 STOC paper was revised into the classic SIAM Journal on Computing version published in February 1989.
Why it worked
- Simulation proves the verifier learns nothing beyond truth
- Random challenges make false proofs fail
- Knowledge complexity unified ideas about proof and secrecy
- It worked for both number theory and graph problems
What can be applied
A proof can transfer confidence without the secret. Define what the other party may learn, then prove the protocol leaks at most that: a vague promise becomes a checkable property.
Aftermath
Zero-knowledge proofs grew into a cornerstone of modern cryptography and complexity theory, as Goldreich's survey 'Zero-Knowledge twenty years after its invention' documents. Decades later the same idea powers zk-SNARKs used in privacy-focused blockchains and verifiable computation.
Sources
- The Knowledge Complexity of Interactive Proof-Systems
- Zero-Knowledge twenty years after its invention
spotted an error? The archive wants to know.