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]).

- For Proofs that Yield Nothing But their Validity
or All Languages in NP have Zero-Knowledge Proofs:
- 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.
- See also Zero-Knowledge: A Tutorial (2002) and a PR poster (2003).

- For How to Solve any Protocol Problem:
- extended abstract, 19th STOC, 1987. (Copyright of ACM)
- a related version preferred by O.G., 1987.
- The contents of this paper is fully covered in
Secure Multi-Party Computation (draft, 1998)
[by Oded Goldreich].

Also covered in Chapter 7 of Foundations of Cryptography (Vol. 2) [by Oded Goldreich].

Back to Oded Goldreich's homepage.