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.
This work is not avialbale on-line,
yet most of the material is covered in
Foundations of Cryptography - Fragments of a Book
[by Oded Goldreich].
(See also
an extract of the relevant part.)

A TUTORIAL ON ZERO-KNOWLEDGE (2002) is available.

The following papers can be obtained in PostScript (papers are ordered by the full author-list):

- B. Barak and O. Goldreich, Universal Arguments and their Applications, 2001.
- B. Barak, O. Goldreich, S. Goldwasser and Y. Lindell, Resettably-Sound Zero-Knowledge and its Applications, 2001.
- M. Bellare and O. Goldreich,
On Defining Proofs of Knowledge, 1992.

See also our notes on Proofs of Computational Ability (1992). - R. Canetti, O. Goldreich, S. Goldwasser and S. Micali, Resettable Zero-Knowledge, 1999.
- I. Damgard, O. Goldreich, T. Okamoto and A. Wigderson,

Honest Verifier vs Dishonest Verifier in Public Coin Zero-Knowledge Proofs (Extended Abstract), September 1995. See also partial version by Damgard, Goldreich, and Wigderson, November 1994. - I. Damgard, O. Goldreich and A. Wigderson,

Information Theory versus Complexity Theory: Another Test Case, September 1995. - O. Goldreich, A Uniform-Complexity Treatment of Encryption and Zero-Knowledge, July 1991.
- O. Goldreich, The Graph Clustering Problem has a Perfect Zero-Knowledge Proof, October 1996.
- O. Goldreich, Concurrent Zero-Knowledge With Timing, Revisited, 2001.
- O. Goldreich and A. Kahan, How to Construct Constant-Round Zero-Knowledge Proof Systems for NP, March 1996.
- O. Goldreich and H. Krawczyk, On the Composition of Zero-Knowledge Proof Systems, revised 1994.
- O. Goldreich and Y. Oren, Definitions and properties of Zero-Knowledge proof systems, an old version (1992?).
- O. Goldreich, A. Sahai and S. Vadhan, Honest-Verifier Statistical Zero-Knowledge Equals General Statistical Zero-Knowledge, 1998.
- O. Goldreich, A. Sahai and S. Vadhan, Can Statistical Zero-Knowledge be Made Non-Interactive? or On the Relationship of SZK and NISZK, 1998.
- O. Goldreich and S. Vadhan, Comparing Entropies in Statistical Zero-Knowledge with Applications to the Structure of this Class, 1998.

Back to Oded Goldreich's homepage or to the full list of papers.