From Weizmann's annual report 2003
The above text is based on the Graph Non-Isomoprphism (zero-knowledge)
proof that was presented by Goldreich, Micali and Wigderson
in Proofs that Yield Nothing But their Validity
or All Languages in NP have Zero-Knowledge Proofs,
Journal of the ACM, July 1991.
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
the aforementioned work.
In particular, assuming the existence of one-way functions,
it is shown that every language in NP has a zero-knowledge proof system.
For further detail on this (and other related) work
see Goldreich's webpage on zero-knowledge.
Back to Oded Goldreich's homepage.