Oded Goldreich

Zero-Knowledge and Secure Computation

The GMW papers - what's available on-line

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, assuming the existence of one-way functions, it is shown that every language in NP has a zero-knowledge proof system.

The dramatic effect of the above work on the design of cryptographic protocols is demonstrated in another paper of the same authors titled How to Solve any Protocol Problem [STOC87]. Using additional ideas, it is shown that any protocol problem can be solved. Specifically, for every N-ary (computable) function F, a fault-tolerant protocol for computing F is constructed. The protocol can tolerate adversarial behaviour of any minority, and no minority can learn from the execution more than it can learn from its own inputs and the value of the function. In other words, the protocol simulates a trusted party in an environment in which no party can be trusted (and furthermore any minority may be malicious). Furthermore, the construction of the fault-tolerant protocol is explicit (in the sense that an efficient algorithm is presented that, on input a Turing machine description of a function, outputs the desired fault-tolerant protocol). This work has also inspired the development and study of cryptographic protocols in the private channel model (cf., work by Ben-Or, Goldwasser and Wigderson [STOC88]).

Material available on-line includes

  1. For Proofs that Yield Nothing But their Validity or All Languages in NP have Zero-Knowledge Proofs:
  2. For How to Solve any Protocol Problem:

Back to Oded Goldreich's homepage.