**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

**Available format(s): **PDF | BibTeX Citation

**Version: **20130915:144900 (All versions of this report)

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]