CryptoDB
On the Existence of 3-Round Zero-Knowledge Protocols
Authors: | |
---|---|
Download: | |
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 }