Cryptology ePrint Archive: Report 2012/508

On the (Im)Plausibility of Constant-Round Public-Coin Straight-Line-Simulatable Zero-Knowledge Proofs

Yi Deng and Juan Garay and San Ling and Huaxiong Wang and Moti Yung

Abstract: 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.

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


[ Cryptology ePrint archive ]