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.
Category / Keywords: foundations / Date: received 2 Sep 2012, last revised 4 Sep 2012 Contact author: garay at research att com Available formats: PDF | BibTeX Citation Version: 20120904:193048 (All versions of this report) Discussion forum: Show discussion | Start new discussion