ECCC-Report TR19-074https://eccc.weizmann.ac.il/report/2019/074Comments and Revisions published for TR19-074en-usWed, 22 May 2019 21:28:29 +0300
Paper TR19-074
| Finding a Nash Equilibrium Is No Easier Than Breaking Fiat-Shamir |
Chethan Kamath,
Arka Rai Choudhuri,
Pavel Hubacek,
Krzysztof Pietrzak,
Alon Rosen,
Guy Rothblum
https://eccc.weizmann.ac.il/report/2019/074 The Fiat-Shamir heuristic transforms a public-coin interactive proof into a non-interactive argument, by replacing the verifier with a cryptographic hash function that is applied to the protocolâ€™s transcript. Constructing hash functions for which this transformation is sound is a central and long-standing open question in cryptography.
We show that solving the End-of-Metered-Line problem is no easier than breaking the soundness of the Fiat-Shamir transformation when applied to the sumcheck protocol. In particular, if the transformed protocol is sound, then any hard problem in #P gives rise to a hard distribution in the class CLS, which is contained in PPAD.
Our main technical contribution is a stateful incrementally verifiable procedure that, given a SAT instance over n variables, counts the number of satisfying assignments. This is accomplished via an exponential sequence of small steps, each computable in time poly(n). Incremental verifiability means that each intermediate state includes a sumcheck-based proof of its correctness, and the proof can be updated and verified in time poly(n).
Combining our construction with a hash family proposed by Canetti et al. [STOC 2019] gives rise to a distribution in the class CLS, which is provably hard under the assumption that any one of a class of fully homomorphic encryption (FHE) schemes has almost-optimal security against quasi-polynomial time adversaries, and under the additional worst-case assumption that there is no polynomial time algorithm for counting the number of satisfying assignments for formulas over a polylogarithmic number of variables. Wed, 22 May 2019 21:28:29 +0300https://eccc.weizmann.ac.il/report/2019/074