Two-message auxiliary-input ZK ⊆ BPP

Inclusion · GO94

Statement

Suppose a language $L$ has a two-message interactive proof or argument (the verifier sends one message and the prover answers) with negligible soundness error that is auxiliary-input zero-knowledge. Then $L\in$ BPP — GO94.

Sketch

Let $V^{\ast }$ be the verifier that sends its auxiliary input $z$ as its message, and let $\mathcal{S}$ be its simulator. To decide $L$ on $x$, sample honest-verifier coins $r$, compute the honest message $q$, run $\mathcal{S}(x,q)$, and accept iff the honest verifier with coins $r$ accepts the answer in the simulated view. On $x\in L$, acceptance is within a negligible amount of the completeness bound, since otherwise a non-uniform distinguisher with suitable coins $r$ hard-wired would tell simulated from real views on auxiliary input $q$. On $x\notin L$, $\mathcal{S}(x,\cdot )$ is an efficient cheating prover, so soundness makes acceptance negligible — standard.

Notes

• The converse inclusion is trivial: every language in $\mathbf{BPP}$ has such a protocol, in which the verifier decides alone — standard.
• Auxiliary-input zero knowledge for a language outside $\mathbf{BPP}$ needs a randomized prover and a randomized verifier, and one-message zero knowledge without setup exists only for languages in $\mathbf{BPP}$ — GO94.
• Without auxiliary input, and under complexity assumptions, $\mathbf{NP}$-complete languages have no two-round zero-knowledge proof with perfect completeness, even with non-black-box simulation — BLV03.