Paper 1999/009

On the Existence of3-Round Zero-Knowledge Protocols

Satoshi Hada and Toshiaki Tanaka

Abstract

In this paper, we construct a 3-round zero-knowledge protocol for any NP language. Our protocol achieves weaker notions of zero-knowledge than black-box simulation zero-knowledge. Therefore, our result does not contradict the triviality result of Goldreich and Krawczyk which shows that 3-round black-box simulation zero-knowledge exist only for BPP languages. Our main contribution is to provide a non-black-box simulation technique. Whether there exists such a simulation technique was a major open problem in the theory of zero-knowledge. Our simulation technique is based on a non-standard computational assumption related to the Diffie-Hellman problem, which was originally proposed by Damgard.

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-knowledgeinteractive proofsinteractive argumentsDiffie-Hellman problemNP.
Contact author(s)
hada @ lab kdd co jp
History
1999-03-31: received
Short URL
https://ia.cr/1999/009
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:1999/009,
      author = {Satoshi Hada and Toshiaki Tanaka},
      title = {On the Existence of3-Round Zero-Knowledge Protocols},
      howpublished = {Cryptology ePrint Archive, Paper 1999/009},
      year = {1999},
      note = {\url{https://eprint.iacr.org/1999/009}},
      url = {https://eprint.iacr.org/1999/009}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.