Constant-round black-box ZK with strict polynomial-time simulation ⊆ BPP

Inclusion · BL02

Statement

Suppose a language $L$ has a constant-round interactive proof or argument with negligible soundness error that is zero-knowledge with a black-box simulator running in strict, not expected, polynomial time. Then $L\in$ BPP — BL02.

Notes

• Constant-round zero knowledge with black-box simulation therefore needs expected polynomial-time simulators, as the simulator of Goldreich–Kahan is — BL02, GK96b. Barak’s constant-round argument (CRHF ⇒ Constant-round ZK argument (Barak)) has a strict polynomial-time simulator that uses the verifier’s code — BL02, Bar01.
• No constant-round zero-knowledge argument of knowledge for a relation outside $\mathbf{BPP}$ has a strict polynomial-time black-box knowledge extractor — BL02.
• With non-negligible soundness error the bound fails: one execution of the 3-coloring protocol of GMW91, whose soundness error is $1-1/|E|$, has a strict polynomial-time black-box simulator that guesses the challenged edge $n|E|$ times — standard.