How to construct zero-knowledge proof systems for NP
Webpage for a paper by Oded Goldreich, Silvio Micali
and Avi Wigderson
Material available on-line
Zero-Knowledge: A Tutorial (2002)
and a PR poster (2003).
Zero-knowledge proofs are probabilistic and interactive proofs that
efficiently demonstrate membership in the language
without conveying any additional knowledge.
The wide applicability of zero-knowledge was demonstrated
in Proofs that Yield Nothing But their Validity
or All Languages in NP have Zero-Knowledge Proofs,
coauthored by Goldreich, Micali and Wigderson [JACM, July 1991].
- It is shown that Graph Isomorphism and Graph Non-Isomorphism
have (perfect) zero-knowledge proof systems.
All previously known zero-knowledge proofs were for sets related
to number theory, and furthermore GNI was the first set not known
to be in NP that was shown to have an interactive proof system.
- Assuming the existence of one-way functions,
it is shown that every language in NP
has a zero-knowledge proof system.
Only few sets were known before to have zero-knowledge proofs
and so the utility of zero-knowledge was previously restricted to
some special cases. In contrast, this result asserts that
zero-knowledge exist for any statement having an NP-proof.
The dramatic effect of this result on the design of cryptographic
protocols is demonstrated in another paper of the same authors;
see webpage on
How to Solve any Multi-Party Protocol Problem.
Back to Oded Goldreich's homepage.