Public-coin black-box ZK under parallel repetition ⊆ BPP

Inclusion · PTW09

Statement

Suppose a language $L$ has a public-coin interactive proof or argument with negligible soundness error that remains black-box zero-knowledge under polynomially many parallel repetitions. Then $L\in$ BPP — PTW09.

Notes

• The converse inclusion is trivial: every language in $\mathbf{BPP}$ has such a protocol, in which the verifier decides alone — standard.
• The bound also holds in the bare public-key model, where prover and verifier have registered public keys — PTW09.
• A sufficiently parallel-repeated public-coin protocol is resettably sound when the verifier derives its coins from a pseudorandom function — PTW09.
• One-way functions give a public-coin black-box zero-knowledge proof that stays zero-knowledge under any a-priori bounded number of concurrent executions — PTW09.
• With a constant number of messages, public-coin black-box zero knowledge exists only for languages in $\mathbf{BPP}$ even without repetition (Constant-round public-coin black-box ZK ⊆ BPP) — GK96a.