**Finding a Nash Equilibrium Is No Easier Than Breaking Fiat-Shamir**

*Arka Rai Choudhuri and Pavel Hubacek and Chethan Kamath and Krzysztof Pietrzak and Alon Rosen and Guy N. Rothblum*

**Abstract: **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.

**Category / Keywords: **foundations / TFNP, PPAD, Nash Equilibrium, Fiat-Shamir transformation

**Original Publication**** (with major differences): **STOC 2019
**DOI: **10.1145/3313276.3316400

**Date: **received 22 May 2019

**Contact author: **achoud at cs jhu edu, hubacek@iuuk mff cuni cz, ckamath@ist ac at, pietrzak@ist ac at, alon rosen@idc ac il, rothblum@alum mit edu

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

**Version: **20190523:063722 (All versions of this report)

**Short URL: **ia.cr/2019/549

[ Cryptology ePrint archive ]