Cryptology ePrint Archive: Report 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.

Category / Keywords: foundations /

Date: received 2 Sep 2012, last revised 15 Sep 2013

Contact author: ydeng cas at gmail com, juan a garay@gmail com, motiyung@gmail com