We 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.