Lower Bounds for NonBlackBox Zero Knowledge
Boaz Barak, Yehuda Lindell and Salil Vadhan
Abstract:
We show new lower bounds and impossibility results for general
(possibly nonblackbox) zeroknowledge proofs and
arguments. Our main results are that, under reasonable
complexity assumptions:

There does not exist a constantround zeroknowledge
strong proof (or argument) of knowledge (as defined by
Goldreich (2001)) for a nontrivial language.

There does not exist a tworound zeroknowledge
proof system with perfect completeness for an
NPcomplete language.
The previous impossibility result for tworound zero knowledge, by
Goldreich and Oren (J. Cryptology, 1994) was only for the case of
auxiliaryinput zeroknowledge proofs and arguments.
 There does not exist a constantround publiccoin
proof system for a nontrivial language that is
resettable zero knowledge. This result also extends to
bounded resettable zero knowledge.
In contrast, we show that under reasonable assumptions, there does
exist such a (computationally sound) argument system that
is boundedresettable zero knowledge.
The complexity assumptions we use are not commonly used in
cryptography. However, in all cases, we show that assumptions
like ours are necessary for the above results.
Most previously known lower bounds, such as those of Goldreich and
Krawczyk (SIAM J. Computing, 1996), were only for
blackbox zero knowledge. However, a result of Barak (FOCS
2001) shows that many (or even most) of these blackbox lower
bounds do not extend to the case of general zero knowledge.
Postscript, gzipped Postscript.
Back Home