Paper 2012/508

On Limitations of Universal Simulation: Constant-Round Public-Coin Zero-Knowledge Proofs Imply Understanding Programs

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

Abstract

In this paper we consider the problem of whether there exist non-trivial constant-round public-coin zero-knowledge (ZK) proofs. We focus on the type of ZK proofs that admit a universal simulator (which handles all malicious verifiers), and show a connection between the existence of such proof systems and a seemingly unrelated ``program understanding'' problem: for a natural class of constant-round public-coin ZK proofs (which we call ``canonical,'' since all known ZK protocols fall into this category), a universal simulator can actually be used (as an oracle) to distinguish a non-trivial property of the verifier's program. Our result can be viewed as new and extended evidence against the existence of constant-round public-coin ZK proofs, since the above program-understanding problem, a typical goal in reverse-engineering attempts, is commonly believed to be notoriously hard---in general, and particularly so in the case of limited straight-line simulators. The earlier negative evidence for the above is Barack, Lindell and Vadhan [FOCS '03]'s result, which was based on the incomparable assumption of the existence of certain entropy-preserving hash functions, now known not to be achievable from standard assumptions. Our reduction combines a careful analysis of the behavior of a set of verifiers in the above protocols and simulation, with a key tool which is an improved structure-preserving version of the well-known Babai-Moran Speedup (de-randomization) Theorem.