On the existence of 3-round zero-knowledge protocols

S Hada, T Tanaka - Advances in Cryptology—CRYPTO'98: 18th Annual …, 1998 - Springer
S Hada, T Tanaka
Advances in Cryptology—CRYPTO'98: 18th Annual International Cryptology …, 1998Springer
In this paper, we construct a 3-round zero-knowledge protocol for any NP language.
Goldreich and Krawczyk proved that a 3-round black-box simulation zero-knowledge
protocol exists only for BPP languages. However, there is no contradiction here. That is, our
proposed protocol achieves a weaker notion of zero-knowledge: auxiliary-input non-uniform
zero-knowledge. Since this notion has not been investigated in the literature, we classify
several zero-knowledge notions including it and discuss the relationships among them. Our …
Abstract
In this paper, we construct a 3-round zero-knowledge protocol for any NP language. Goldreich and Krawczyk proved that a 3-round black-box simulation zero-knowledge protocol exists only for BPP languages. However, there is no contradiction here. That is, our proposed protocol achieves a weaker notion of zero-knowledge: auxiliary-input non-uniform zero-knowledge. Since this notion has not been investigated in the literature, we classify several zero-knowledge notions including it and discuss the relationships among them. Our main contribution is to provide a non-black-box simulation technique. It is based on a novel computational assumption related to the Diffie-Hellman problem. Although this assumption is strong and non-standard, its non-standard nature seems essential for our simulation technique.
Springer