Paper 2012/508
On the Implausibility of ConstantRound PublicCoin ZeroKnowledge Proofs
Yi Deng, Juan Garay, San Ling, Huaxiong Wang, and Moti Yung
Abstract
We consider the problem of whether there exist nontrivial constantround publiccoin zeroknowledge (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 constantround publiccoin 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 nontrivial property of the nextstep functionality of the verifier’s code. Our result can be viewed as extended new evidence against the existence of constantround publiccoin 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 programunderstanding problem, a typical goal in reverseengineering attempts, commonly believed to be notoriously hard, or (2) a rather unfathomable simulation strategy beyond the only known (straightline simulation) technique for their argument counterpart, as we also argue. Earlier negative evidence on constantround publiccoin ZK proofs is Barack, Lindell and Vadhan [FOCS ’03]’s result, which was based on the incomparable assumption of the existence of certain entropypreserving hash functions, now (due to further work) known not to be achievable from standard assumptions via blackbox reduction. The core of our technical contribution is showing that there exists a single verifier step for constantround publiccoin 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 structurepreserving version of the wellknown BabaiMoran Speedup (derandomization) Theorem, a key tool of independent interest.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Published elsewhere. Major revision. 10th Conference on Security and Privacy for Networks (SCN 2016)
 Keywords
 Zero knowledge
 Contact author(s)
 juan a garay @ gmail com
 History
 20160719: last of 5 revisions
 20120903: received
 See all versions
 Short URL
 https://ia.cr/2012/508
 License

CC BY
BibTeX
@misc{cryptoeprint:2012/508, author = {Yi Deng and Juan Garay and San Ling and Huaxiong Wang and Moti Yung}, title = {On the Implausibility of ConstantRound PublicCoin ZeroKnowledge Proofs}, howpublished = {Cryptology {ePrint} Archive, Paper 2012/508}, year = {2012}, url = {https://eprint.iacr.org/2012/508} }