Lower bounds for non-black-box zero knowledge

Abstract

We show new lower bounds and impossibility results for general (possibly non-black-box) zero-knowledge proofs and arguments. Our main results are that, under reasonable complexity assumptions: 1. There does not exist a two-round zero-knowledge proof 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 auxiliary-input zero-knowledge proofs and arguments. 2. There does not exist a constant-round zero-knowledge strong proof or argument of knowledge (as defined by Goldreich (2001)) for a nontrivial language. 3. There does not exist a constant-round public-coin proof system for a nontrivial language that is resettable zero knowledge. 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.