Paper 1999/009

On the Existence of3-Round Zero-Knowledge Protocols

Satoshi Hada and Toshiaki Tanaka


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.

Available format(s)
Publication info
Published elsewhere. Appeared in the THEORY OF CRYPTOGRAPHY LIBRARY and has been included in the ePrint Archive.
Zero-knowledgeinteractive proofsinteractive argumentsDiffie-Hellman problemNP.
Contact author(s)
hada @ lab kdd co jp
1999-03-31: received
Short URL
Creative Commons Attribution


      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{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.