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

Abstract

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 straight-line simulator. Since then, however, we have witnessed little progress on the basic question whether Barak’s technique can be extended to ZK 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 without executing the target 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 ϵ, then there exist (p/O(log 1