Round-optimal zero-knowledge arguments based on any one-way function

Authors: M. Bellare, M. Jakobsson and M. Yung

Abstract: We fill a gap in the theory of zero-knowledge protocols by presenting NP-arguments that achieve negligible error probability and computational zero-knowledge in four rounds of interaction, assuming only the existence of a one-way function. This result is optimal in the sense that four rounds and a one-way function are each individually necessary to achieve a negligible error zero-knowledge argument for NP.

Ref: Extended abstract was in Advances in Cryptology- Eurocrypt 97 Proceedings, Lecture Notes in Computer Science Vol. 1233, W. Fumy ed, Springer-Verlag, 1997. A revised version, correcting some mistakes in the abstract, is available below.

Full paper: Available as compressed postscript or postscript. ( Help if this doesn't work).