Paper 2012/508

On the Implausibility of Constant-Round Public-Coin Zero-Knowledge Proofs

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


We consider the problem of whether there exist non-trivial constant-round public-coin zero-knowledge (ZK) proofs. To date, in spite of high interest in the above, there is no definite answer to the question. 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 session prefix output by the universal simulator can actually be used to distinguish a non-trivial property of the next-step functionality of the verifier’s code. Our result can be viewed as extended new evidence against the existence of constant-round public-coin ZK proofs, since the existence of such a proof system will bring about either one of the following: (1) a positive result for the above program-understanding problem, a typical goal in reverse-engineering attempts, commonly believed to be notoriously hard, or (2) a rather unfathomable simulation strategy beyond the only known (straight-line simulation) technique for their argument counterpart, as we also argue. Earlier negative evidence on constant-round public-coin ZK proofs 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 (due to further work) known not to be achievable from standard assumptions via black-box reduction. The core of our technical contribution is showing that there exists a single verifier step for constant-round public-coin ZK proofs whose functionality (rather than its code) is crucial for a successful simulation. This is proved by combining a careful analysis of the behavior of a set of verifiers in the above protocols and during simulation, with an improved structure-preserving version of the well-known Babai-Moran Speedup (de-randomization) Theorem, a key tool of independent interest.

Available format(s)
Publication info
Published elsewhere. MAJOR revision.10th Conference on Security and Privacy for Networks (SCN 2016)
Zero knowledge
Contact author(s)
juan a garay @ gmail com
2016-07-19: last of 5 revisions
2012-09-03: received
See all versions
Short URL
Creative Commons Attribution


      author = {Yi Deng and Juan Garay and San Ling and Huaxiong Wang and Moti Yung},
      title = {On the Implausibility of Constant-Round Public-Coin Zero-Knowledge Proofs},
      howpublished = {Cryptology ePrint Archive, Paper 2012/508},
      year = {2012},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.