Black-Box Simulators and the 3-Round Lower Bound
Soon after the discovery of zero-knowledge (but before the discovery of the protocol from the
previous section), people began wondering whether it was possible to design a constant-round
zero-knowledge protocol with negligible soundness (rather than having to amplify soundness by
repeating the basic protocol poly(n) times in sequence). Goldreich and Oren showed that a
three-round protocol cannot have a zero-knowledge simulator of a very natural type (such as all
of the simulators we have seen). In this section we define black-box simulators and work through
the proof of their lower bound.
Three Round Protocols. We use the following notation for a 3-round proof system II for
a language L. We denote the transcript by (T1, T2, T3), and B outputs B(1, 1, 2, 3) E {0, 1}
indicating that he either accepts or rejects A's proof. We say that II is ε-sound if for all x L
and all 1, Pr 3 st B(1, T1, T2, T3) = 1] < E.
Zero-Knowledge Simulators. With the above syntax, a zero-knowledge simulator SIM takes
z as input, uses oracle access to B*, and outputs (#1, #2, #3). Recall we say II is zero-knowledge
if for all z L, the output of SIM (r) is indistinguishable from the transcript resulting from an
interaction between B* and an honest A on input z (and A gets a witness w as extra input).
Black-Box Simulators. We say that a zero-knowledge simulator is black-box if it only makes
"black-box" use of the adversary B (ie., it uses B only as a black-box input/output ma-
chine). Specifically, a black-box simulator, given z, generates some k = poly(n) first messages
(1) (2)
(possibly adaptively), computes = B*() and then generates and out-
puts (,,) for some i. So intuitively, a black-box simulator is only allowed to perform
polynomial time computations using oracle access to B*.
Languages in BPP. A language LC {0, 1}* is in BPP if there exists an efficient randomized
algorithm A such that for all z EL, Pr[A(r) = 1] = 1-negl(n), while for all x L, Pr[A(x) =
1] = negl(n). Intuitively, BPP is the set of languages which can be efficiently decided by a
randomized algorithm.
Theorem. If II is a 3-round proof system for L with negligible soundness and SIM is a black-box
zero-knowledge simulator, then Le BPP.
12
Problem 5. Complete the proof that Le BPP by completing the following outline.
(a) Suppose II is a 3-round proof system for L and that SIM is a black-box zero-knowledge
simulator. Consider the efficient randomized algorithm SIMB which is SIM run with oracle
access to an honest B. Show that when ze L, SIM (2) outputs (T1, T2, T3) such that
B(x, 1, 2, 3) = 1 with probability 1.
(b) Next, show that if SIM is a blackbox simulator such that there exists r L such that
SIMB (2) outputs (1, 2, 3) such that B(1, 1, 2, 3) = 1 holds with non-negligible prob-
ability, then there exists an efficient A* who can convince the honest B to accept a (false)
proof that ЄL with non-negligible probability. This violates the assumption that II has
negligible soundness error.
(c) Deduce that LЄ BPP.