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