[GMW91] Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems

Authors: Oded Goldreich, Silvio Micali, Avi Wigderson | Venue: JACM 1991 | Source

Abstract

We present a general technique for the design of cryptographic protocols. The technique is based on the notion of zero-knowledge proofs, which are proofs that yield nothing but their validity. We show that if all languages in NP have zero-knowledge proof systems, then any function that can be computed in probabilistic polynomial time can be computed in a way that is secure against any computationally bounded adversary. The protocols we construct are fault tolerant in the sense that they can tolerate a certain number of faulty processors. We also show how to use our technique to design protocols for various cryptographic tasks, such as oblivious transfer and secure multiparty computation.

BibTeX

Copy

@Article{GolMicWig91,
  author = {Oded Goldreich and Silvio Micali and Avi Wigderson},
  title = {Proofs That Yield Nothing But Their Validity Or All Languages in {NP} Have Zero-Knowledge Proof Systems},
  pages = {691--729},
  journal = {Journal of the {ACM}},
  volume = {38},
  number = {3},
  month = {jul},
  year = {1991},
  doi = {10.1145/116825.116852},
  annote = {Full version of \cite{FOCS:GolMicWig86}},
}