$next$ $up$ $previous$
Next: Towards a Theory of Up: The Post-Doctoral Period (1983-86) Previous: Two Remarks Concerning the

Proofs that Yield Nothing But their Validity or All Languages in NP have Zero-Knowledge Proofs

This work demonstrates the wide applicability of the notion of zero-knowledge. Most importantly, using any commitment scheme, it is show how to transform any NP-proof system into a zero-knowledge interactive proof system. In addition, a perfect zero-knowledge proof is presented for Graph Isomorphism, and a constant-round interactive proof is presented for the complement set (which is not known to be in NP).

$\fbox{\begin{minipage}{40em} {\bf Abstract ({v.o.}):} {In this paper we demonst... ...umber-theoretic languages in the intersection of NP and CoNP.} \end{minipage}}$

Comments: Authored by O. Goldreich, S. Micali and A. Wigderson. Appeared in

Proc. of the 27th FOCS, pp. 174-187, 1986.
Jour. of the ACM, Vol. 38, No. 3, July 1991, pp. 691-729.

Oded Goldreich
2003-07-30