Finding a Nash equilibrium is no easier than breaking Fiat-Shamir
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F19%3A10404863" target="_blank" >RIV/00216208:11320/19:10404863 - isvavai.cz</a>
Result on the web
<a href="https://doi.org/10.1145/3313276.3316400" target="_blank" >https://doi.org/10.1145/3313276.3316400</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1145/3313276.3316400" target="_blank" >10.1145/3313276.3316400</a>
Alternative languages
Result language
angličtina
Original language name
Finding a Nash equilibrium is no easier than breaking Fiat-Shamir
Original language description
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).
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
<a href="/en/project/GA17-09142S" target="_blank" >GA17-09142S: Modern algorithms: New challenges of complex data sets</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2019
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing
ISBN
978-1-4503-6705-9
ISSN
0737-8017
e-ISSN
—
Number of pages
12
Pages from-to
1103-1114
Publisher name
ACM SIGACT
Place of publication
Neuveden
Event location
Phoenix, AZ, USA
Event date
Jun 23, 2019
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—