Few-round black-box concurrent ZK ⊆ BPP

Inclusion · CKPR01

Statement

Suppose a language $L$ has a $k(n)$-round interactive proof or argument with negligible soundness error, with $k(n)=o(\log n/\log \log n)$, whose concurrent executions are zero-knowledge with a black-box simulator (black-box concurrent zero knowledge in few rounds). Then $L\in$ BPP — CKPR01. So black-box concurrent zero knowledge for a language outside $\mathbf{BPP}$ needs $\tilde{\Omega }(\log n)$ rounds, and in particular more than a constant number — CKPR01.

Notes

• The lower bound is $\Omega (\log n/\log \log n)$ rounds and the upper bound is any $\omega (\log n)$ rounds (OWF ⇒ Concurrent ZK arguments for NP in ω(log n) rounds, Claw-free permutations ⇒ Concurrent ZK proofs for NP in ω(log n) rounds), so the gap is an $\omega (\log \log n)$ factor — PRS02.
• Earlier bounds: no four-message zero-knowledge proof or argument for a language outside $\mathbf{BPP}$ is black-box simulatable under concurrent composition — KPR98 — and the bound was raised before CKPR01 by Ros00.
• Non-black-box simulation gets around the bound: assuming collision-resistant hash functions, one-way permutations and indistinguishability obfuscation for $P/poly$ with slightly super-polynomial security, $\mathbf{NP}$ has constant-round concurrent zero-knowledge protocols — CLP15.
• Under an $(\alpha ,\beta )$ timing constraint on the adversary’s control of clocks, every language in $\mathbf{NP}$ has four-round almost concurrent zero-knowledge proofs and perfect concurrent zero-knowledge arguments — DNS98, who introduced concurrent zero knowledge.