TY - CHAP
T1 - On the implausibility of constant-round public-coin zero-knowledge proofs
AU - Deng, Yi
AU - Garay, Juan
AU - Ling, San
AU - Wang, Huaxiong
AU - Yung, Moti
PY - 2016
Y1 - 2016
N2 - 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 problem, 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 functionality distinguishing” 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 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 functionality-distinguishing problem, a typical goal in reverse-engineering attempts, commonly believed to be notoriously hard, or (2) a major paradigm shift in simulation strategies, beyond the only known (straight-line simulation) technique applicable to their argument counterpart, as we also argue. Note that the earlier negative evidence on constant-round public-coin ZK proofs is Barack, Lindell and Vadhan [FOCS 2003]’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 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.
AB - 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 problem, 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 functionality distinguishing” 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 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 functionality-distinguishing problem, a typical goal in reverse-engineering attempts, commonly believed to be notoriously hard, or (2) a major paradigm shift in simulation strategies, beyond the only known (straight-line simulation) technique applicable to their argument counterpart, as we also argue. Note that the earlier negative evidence on constant-round public-coin ZK proofs is Barack, Lindell and Vadhan [FOCS 2003]’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 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.
UR - http://www.scopus.com/inward/record.url?scp=84984824893&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-44618-9_13
DO - 10.1007/978-3-319-44618-9_13
M3 - Chapter
AN - SCOPUS:84984824893
SN - 9783319446172
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 237
EP - 253
BT - Security and cryptography for networks
A2 - Zikas, Vassilis
A2 - De Prisco, Roberto
PB - Springer, Springer Nature
CY - Cham, Switzerland
T2 - 10th International Conference on Security and Cryptography for Networks, SCN 2016
Y2 - 31 August 2016 through 2 September 2016
ER -