Constant-round public-coin black-box ZK ⊆ BPP

Inclusion · GK96a

Statement

If a language $L$ has a public-coin interactive proof or argument with a constant number of messages and negligible soundness error that is black-box zero-knowledge, then $L\in$ BPP — GK96a. So constant-round public-coin zero-knowledge arguments for $\mathbf{NP}$ with black-box simulation exist only if $\mathbf{NP}\subseteq \mathbf{BPP}$.

Sketch

GK96a run the black-box simulator, truncated at $q=\mathrm{poly}(n)$ queries, against a cheating verifier that computes each message by applying a function drawn from a $q$-wise independent family to the transcript so far, and accept iff the simulated transcript is accepting. On $x\in L$ the transcript is accepting by completeness and zero knowledge, since the coins are public and acceptance is checkable from the transcript. On $x\notin L$, suppose 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 $c=O(1)$ rounds, so negligible soundness error makes $p$ negligible.

Notes

• The converse inclusion is trivial: every language in $\mathbf{BPP}$ has such a protocol, in which the verifier decides alone, so the class equals $\mathbf{BPP}$ — standard.
• Non-black-box simulation gets around the bound: assuming collision-resistant hash functions, $\mathbf{NP}$ has a constant-round public-coin zero-knowledge argument with negligible soundness error (CRHF ⇒ Constant-round ZK argument (Barak)) — Bar01.
• Without the constant-round restriction, public-coin black-box zero knowledge that survives polynomially many parallel repetitions also exists only for languages in $\mathbf{BPP}$ (Public-coin black-box ZK under parallel repetition ⊆ BPP) — PTW09.
• Under assumptions on program obfuscation, constant-round public-coin zero-knowledge proofs for $\mathbf{NP}$ do not exist even with non-black-box simulation — KRR17.