International Association
for Cryptologic Research

In 2001, a breakthrough result by Barak [FOCS 2001] showed how to

achieve public-coin zero-knowledge (ZK) arguments in constant rounds,

a feature known to be impossible using black-box simulation. In this

approach, the simulator makes use of the code of the malicious

verifier in computing the prover messages (albeit without

understanding it), and does not rewind the malicious verifier---and it

is hence called a \\emph{straight-line} simulator.

Since then, however, we have witnessed little progress on the basic

question whether Barak\'s technique can be extended to ZK {\\em proof}

systems. In this paper we make progress on this front, by providing

strong evidence that such an extension is far from likely.

Specifically, we show that for a natural class of constant-round

public-coin ZK proofs (which we call ``canonical,\'\' as all known

non-black-box ZK protocols fall in this category), a straight-line

simulator based on the known non-black-box technique for such a proof

system can actually be used to solve a seemingly unrelated problem,

namely, to figure out some non-trivial property of a verifier\'s

program, and {\\em without executing the targe code}, a problem

commonly viewed as notoriously hard.

A key tool in our reduction is an improved structure-preserving

version of the well-known Babai-Moran Speedup (derandomization)

Theorem, which essentially says that, for a constant-round public-coin

interactive proof system in which the verifier sends $m$ messages and

each of the prover messages is of length $p$, if the cheating

probability for an unbounded prover is $\\epsilon$, then there exist

$(p/O(\\log \\frac{1}{\\epsilon}))^m$ verifier random tapes such that the

cheating probability for the unbounded prover over these random tapes

is bounded away from 1---and this holds even when the prover knows

this small set of random tapes in advance. (In our setting, the

original Babai-Moran theorem yields a much larger size ($(O(p))^m$) of

such set of verifier random tapes.) In addition, we show that this is

tight with respect to round complexity, in the sense that there are

public-coin proof systems with a super-constant number of rounds for

which the prover\'s cheating probability is $1$, over any polynomial

number of verifier random tapes.

Finally, although the notion of straight-line simulation is

intuitively clear and has been used several times in the literature,

we are not aware of a formal definition of the process, perhaps due to

the fact that thoroughly defining (as well as enforcing) ``executing

the verifier only once\'\' does not appear to be straightforward. The

notion of {\\em generalized straight-line simulation} that we introduce

not only overcomes those obstacles, but enables us to expose the

limitations of the currently known non-black-box techniques.