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 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 zeroknowledge strong proof or argument of
knowledge (as defined by Goldreich (2001)) for a nontrivial language.
 There does not exist a constantround publiccoin proof system for a nontrivial
language that is resettable zero knowledge. This result also extends to "boundedresettable"
zero knowledge, in which the number of resets is a priori bounded by a
polynomial in the input length and provertoverifier communication. 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 similar to 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.
Versions

Extended abstract in Proceedings of the 44th Annual Symposium on Foundations
of Computer Science (FOCS `03), pages 384393, Cambridge, MA, October 2003.
IEEE. [official
IEEE page]

Electronic Colloquium on Computational Complexity (ECCC), technical
report TR04083. September 2004. [ECCC
page]
Cryptology ePrint Archive, Report 2004/226. September 2004.
[ePrint page]

Journal of Computer and System Sciences, 72(2):321391,
March 2006. Special Issue on FOCS `03. [official
JCSS page][postscript][pdf]
[
back to Salil Vadhan's research]