# Finding a Nash equilibrium is no easier than breaking Fiat-Shamir

Choudhuri AR, Hubáček P, Kamath Hosdurg C, Pietrzak KZ, Rosen A, Rothblum GN. 2019. Finding a Nash equilibrium is no easier than breaking Fiat-Shamir. Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing - STOC 2019. STOC: Symposium on Theory of Computing, 1103–1114.

Download (ext.)

https://eprint.iacr.org/2019/549
[Preprint]

*Conference Paper*|

*Published*|

*English*

**Scopus indexed**

Author

Choudhuri, Arka Rai;
Hubáček, Pavel;
Kamath Hosdurg, Chethan

^{ISTA}; Pietrzak, Krzysztof Z^{ISTA}^{}; Rosen, Alon; Rothblum, Guy N.Department

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 result opens up the possibility of sampling moderately-sized games for which it is hard to find a Nash equilibrium, by reducing the inversion of appropriately chosen one-way functions to #SAT.
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).

Publishing Year

Date Published

2019-06-01

Proceedings Title

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing - STOC 2019

Page

1103-1114

Conference

STOC: Symposium on Theory of Computing

Conference Location

Phoenix, AZ, United States

Conference Date

2019-06-23 – 2019-06-26

ISBN

IST-REx-ID

### Cite this

Choudhuri AR, Hubáček P, Kamath Hosdurg C, Pietrzak KZ, Rosen A, Rothblum GN. Finding a Nash equilibrium is no easier than breaking Fiat-Shamir. In:

*Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing - STOC 2019*. ACM Press; 2019:1103-1114. doi:10.1145/3313276.3316400Choudhuri, A. R., Hubáček, P., Kamath Hosdurg, C., Pietrzak, K. Z., Rosen, A., & Rothblum, G. N. (2019). Finding a Nash equilibrium is no easier than breaking Fiat-Shamir. In

*Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing - STOC 2019*(pp. 1103–1114). Phoenix, AZ, United States: ACM Press. https://doi.org/10.1145/3313276.3316400Choudhuri, Arka Rai, Pavel Hubáček, Chethan Kamath Hosdurg, Krzysztof Z Pietrzak, Alon Rosen, and Guy N. Rothblum. “Finding a Nash Equilibrium Is No Easier than Breaking Fiat-Shamir.” In

*Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing - STOC 2019*, 1103–14. ACM Press, 2019. https://doi.org/10.1145/3313276.3316400.A. R. Choudhuri, P. Hubáček, C. Kamath Hosdurg, K. Z. Pietrzak, A. Rosen, and G. N. Rothblum, “Finding a Nash equilibrium is no easier than breaking Fiat-Shamir,” in

*Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing - STOC 2019*, Phoenix, AZ, United States, 2019, pp. 1103–1114.Choudhuri, Arka Rai, et al. “Finding a Nash Equilibrium Is No Easier than Breaking Fiat-Shamir.”

*Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing - STOC 2019*, ACM Press, 2019, pp. 1103–14, doi:10.1145/3313276.3316400.**All files available under the following license(s):**

**Copyright Statement:**

**This Item is protected by copyright and/or related rights.**[...]

**Link(s) to Main File(s)**

Access Level

Open Access

**Material in ISTA:**

**Dissertation containing ISTA record**

### Export

Marked PublicationsOpen Data ISTA Research Explorer