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

See also 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]. In particular:

Back to Oded Goldreich's homepage.