Paper 1997/002

Round-Optimal Zero-Knowledge Arguments Based on any One-Way Function

Mihir Bellare, 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.

Metadata
Available format(s)
PS
Publication info
Published elsewhere. Appeared in the THEORY OF CRYPTOGRAPHY LIBRARY and has been included in the ePrint Archive.
Keywords
Zero-knowledgeone-way functionsargumentsround
Contact author(s)
mihir @ cs ucsd edu
History
1997-02-26: received
Short URL
https://ia.cr/1997/002
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:1997/002,
      author = {Mihir Bellare and Markus Jakobsson and Moti Yung},
      title = {Round-Optimal Zero-Knowledge Arguments Based on any One-Way Function},
      howpublished = {Cryptology ePrint Archive, Paper 1997/002},
      year = {1997},
      note = {\url{https://eprint.iacr.org/1997/002}},
      url = {https://eprint.iacr.org/1997/002}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.