International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

On the Existence of 3-Round Zero-Knowledge Protocols

Authors:
Satoshi Hada
Toshiaki Tanaka
Download:
URL: http://eprint.iacr.org/1999/009
Search ePrint
Search Google
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.
BibTeX
@misc{eprint-1999-11331,
  title={On the Existence of	3-Round Zero-Knowledge Protocols},
  booktitle={IACR Eprint archive},
  keywords={Zero-knowledge, interactive proofs, interactive arguments, Diffie-Hellman problem, NP.},
  url={http://eprint.iacr.org/1999/009},
  note={Appeared in the THEORY OF CRYPTOGRAPHY LIBRARY and has been included in the ePrint Archive. hada@lab.kdd.co.jp 10500 received March 31, 1999. An earlier version has appeared in CRYPTO'98.},
  author={Satoshi Hada and Toshiaki Tanaka},
  year=1999
}