Cryptology ePrint Archive: Report 1999/009
On the Existence of 3-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
Category / Keywords: Zero-knowledge, interactive proofs, interactive arguments, Diffie-Hellman problem, NP.
Publication Info: Appeared in the THEORY OF CRYPTOGRAPHY LIBRARY and has been included in the ePrint Archive.
Date: received March 31, 1999. An earlier version has appeared in CRYPTO'98.
Contact author: hada at lab kdd co jp
Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | BibTeX Citation
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]