No reduction from ZKP to Argument systems

Unconditional · GK96a

Statement

No language outside BPP has a constant-round public-coin zero-knowledge proof or argument with negligible soundness error whose simulator uses the cheating verifier only as an oracle, and none has a three-round one, public-coin or not — GK96a. Constant-round public-coin zero-knowledge arguments for $\mathbf{NP}$ with negligible soundness error and black-box simulation therefore exist only if $\mathbf{NP}\subseteq \mathbf{BPP}$.

Sketch

For the public-coin case, GK96a run the black-box simulator against a cheating verifier whose coins are a random function of the transcript so far, and accept iff the simulated transcript is accepting. On $x\in L$ it is accepting by completeness and zero knowledge. On $x\notin L$, if the simulated transcript is accepting with probability $p$, a cheating prover that runs the simulator and forwards one guessed query per round to the real verifier convinces it with probability at least $p/q^c$ for $q$ simulator queries and $c=O(1)$ rounds, so negligible soundness error makes $p$ negligible.

Notes

• Non-black-box simulation gets around the barrier: assuming collision-resistant hash functions, $\mathbf{NP}$ has a constant-round public-coin zero-knowledge argument with negligible soundness error whose simulator uses the cheating verifier’s code (CRHF ⇒ Constant-round ZK argument (Barak)) — Bar01.