Three-message black-box ZK ⊆ BPP

Inclusion · GK96a

Statement

If a language $L$ has a three-message interactive proof or argument with negligible soundness error that is black-box zero-knowledge — one expected-polynomial-time oracle machine $\mathcal{S}$ such that for every efficient $V^{\ast }$ and every $x\in L$, ${\mathcal{S}}^{V^{\ast }}(x)$ is computationally indistinguishable from the view of $V^{\ast }$ — then $L\in$ BPP. This holds for private-coin and public-coin protocols alike — GK96a. So no $\mathbf{NP}$-complete language has such a protocol unless $\mathbf{NP}\subseteq \mathbf{BPP}$.

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.
• For arguments the bound is tight: four-message zero-knowledge arguments for $\mathbf{NP}$ exist from any one-way function (OWF ⇒ Four-message ZK arguments for NP) — BJY97 — and with a fully black-box construction from injective one-way functions (Injective OWF ⇒ Four-message ZK arguments for NP (fully black-box)) — HV18, KOS18. For proofs, four messages put $L$ in coMA (Four-message black-box ZK proofs ⊆ coMA) — Kat08 — and five messages suffice from claw-free permutations (Claw-free permutations ⇒ Constant-round ZK proofs for NP (Goldreich–Kahan)) — GK96b.
• Non-black-box simulation gets around the bound: under the discrete-logarithm assumption and KEA3 in one prime-order group, $\mathbf{NP}$ has three-message zero-knowledge arguments (DLOG + KEA3 ⇒ Three-message ZK arguments for NP) — BP04, repairing HT98.
• Under assumptions on program obfuscation, three-message private-coin zero-knowledge proofs for $\mathbf{NP}$ do not exist even with non-black-box simulation — FGJ18.