Paper 1999/009 Original: eprint.iacr.org/1999/009 ↗
On the Existence of3-Round Zero-Knowledge Protocols
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)
PDF- Publication info
- Preprint.
- History
- 1999-03-31: last updated
- 1999-03-31: published
- Short URL
- https://ia.cr/1999/009
- License
- https://creativecommons.org/licenses/by/4.0/
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},
url = {https://eprint.iacr.org/1999/009}
}