Lower Bounds for Non-Black-Box Zero Knowledge

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 constant-round zero-knowledge strong proof (or argument) of knowledge (as defined by Goldreich, 2001) for a nontrivial language; 2. There does not exist a two-round zero-knowledge proof system with perfect completeness for an NP-complete 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 contrast, we show that under reasonable assumptions, there does exist such a (computationally sound) argument system that is bounded-resettable zero knowledge.

Authors

• Boaz Barak
• Yehuda Lindell
• Salil P. Vadhan

Keywords

• Cryptography
• Computer science
• Access protocols
• Lower Bound
• Zero Knowledge
• Reasonable Assumption
• Strong Proof
• Zero-knowledge Proof
• Running Time
• Error Function
• Case Of System
• Strong Argument
• Hash Function
• Soundproof
• Efficient Procedure
• Standard Assumptions
• Probability 1
• Encryption Scheme
• Non-deterministic Polynomial-time
• Random Bits
• Input Bits
• Random String
• One-way Function
• Probabilistic Polynomial Time
• Non-negligible Probability