ECCC-Report TR04-083https://eccc.weizmann.ac.il/report/2004/083Comments and Revisions published for TR04-083en-usMon, 27 Sep 2004 17:08:07 +0200
Paper TR04-083
| Lower Bounds for Non-Black-Box Zero Knowledge |
Boaz Barak,
Yehuda Lindell,
Salil Vadhan
https://eccc.weizmann.ac.il/report/2004/083We show new lower bounds and impossibility results for general (possibly <i>non-black-box</i>) zero-knowledge proofs and arguments. Our main results are that, under reasonable complexity assumptions:
<ol>
<li> There does not exist a two-round zero-knowledge <i>proof</i> system with perfect completeness for an NP-complete language. The previous impossibility result for two-round zero knowledge, by Goldreich and Oren (J. Cryptology, 1994) was only for the case of <i>auxiliary-input</i> zero-knowledge proofs and arguments.
<li> There does not exist a constant-round zero-knowledge <i>strong</i> proof or argument of knowledge (as defined by Goldreich (2001)) for a nontrivial language.
<li> There does not exist a constant-round public-coin <i>proof</i> system for a nontrivial language that is <i>resettable zero knowledge</i>. This result also extends to "bounded-resettable" zero knowledge, in which the number of resets is a priori bounded by a polynomial in the input length and prover-to-verifier communication. In contrast, we show that under reasonable assumptions, there does exist such a (computationally sound) <i>argument</i> system that is bounded-resettable zero knowledge.
</ol>
<p>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.
<p>Most previously known lower bounds, such as those of Goldreich and Krawczyk (SIAM J. Computing, 1996), were only for <i>black-box</i> zero knowledge. However, a result of Barak (FOCS 2001) shows that many (or even most) of these black-box lower bounds do <i>not</i> extend to the case of general zero knowledge.
Mon, 27 Sep 2004 17:08:07 +0200https://eccc.weizmann.ac.il/report/2004/083