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

• extended abstract, 27th FOCS, 1986. (Copyright of IEEE)
• final version, JACM, Vol. 38, No. 3, July 1991. (Copyright of ACM)
• Most of the contents of this paper is covered in Chapter 4 of Foundations of Cryptography (Vol. 1) [by Oded Goldreich]. See also an extract of an old version of the relevant part.

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:

• 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.