Round-Optimal Zero-Knowledge Arguments Based on any One-Way Function
Mihir Bellare and Markus Jakobsson and Moti 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.
Keywords: Zero-knowledge, one-way functions, arguments, round complexity.
comment: received February 26th, 1997. Revised July 18th, 1997.
contact author: mihir@cs.ucsd.edu
Fetch PostScript file of the full (rev.) paper.