TY - GEN
T1 - PPAD is as Hard as LWE and Iterated Squaring
AU - Bitansky, Nir
AU - Choudhuri, Arka Rai
AU - Holmgren, Justin
AU - Kamath, Chethan
AU - Lombardi, Alex
AU - Paneth, Omer
AU - Rothblum, Ron D.
N1 - Funding Information:
Alex Lombardi is supported in part by DARPA under Agreement No. HR00112020023, a grant from MIT-IBM Watson AI, a grant from Analog Devices, a Microsoft Trustworthy AI grant, the Thornton Family Faculty Research Innovation Fellowship and a Charles M. Vest fellowship. Any opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the United States Government or DARPA.
Funding Information:
Acknowledgements. Nir Bitansky is a member of the checkpoint institute of information security and is supported by the European Research Council (ERC) under the European Union’s Horizon Europe research and innovation programme (grant agreement No. 101042417, acronym SPP), and by Len Blavatnik and the Blavatnik Family Foundation.
Funding Information:
Ron Rothblum was funded by the European Union. Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council. Neither the European Union nor the granting authority can be held responsible for them.
Funding Information:
Omer Paneth is a member of the checkpoint institute of information security and is supported by an Azrieli Faculty Fellowship, Len Blavatnik and the Blavatnik Foundation, the Blavatnik Interdisciplinary Cyber Research Center at Tel Aviv University, and ISF grant 1789/19.
Funding Information:
Chethan Kamath is supported by Azrieli International Postdoctoral Fellowship and ISF grants 484/18 and 1789/19. He thanks Alexandros Hollender and Ninad Rajagopal for discussions on the class UEOPL and Krzysztof Pietrzak for clarifications about unique VDFs.
Funding Information:
Arka Rai Choudhuri is supported in part by DARPA under Agreement No. HR00112020026, AFOSR Award FA9550-19-1-0200, NSF CNS Award 1936826, and research grants by the Sloan Foundation, and Visa Inc. Any opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the United States Government or DARPA.
Publisher Copyright:
© 2022, The Author(s), under exclusive license to Springer Nature Switzerland AG.
PY - 2022
Y1 - 2022
N2 - One of the most fundamental results in game theory is that every finite strategic game has a Nash equilibrium, an assignment of (randomized) strategies to players with the stability property that no individual player can benefit from deviating from the assigned strategy. It is not known how to efficiently compute such a Nash equilibrium—the computational complexity of this task is characterized by the class PPAD, but the relation of PPAD to other problems and well-known complexity classes is not precisely understood. In recent years there has been mounting evidence, based on cryptographic tools and techniques, showing the hardness of PPAD. We continue this line of research by showing that PPAD is as hard as learning with errors (LWE) and the iterated squaring (IS) problem, two standard problems in cryptography. Our work improves over prior hardness results that relied either on (1) sub-exponential assumptions, or (2) relied on “obfustopia,” which can currently be based on a particular combination of three assumptions. Our work additionally establishes public-coin hardness for PPAD (computational hardness for a publicly sampleable distribution of instances) that seems out of reach of the obfustopia approach. Following the work of Choudhuri et al. (STOC 2019) and subsequent works, our hardness result is obtained by constructing an unambiguous and incrementally-updateable succinct non-interactive argument for IS, whose soundness relies on polynomial hardness of LWE. The result also implies a verifiable delay function with unique proofs, which may be of independent interest.
AB - One of the most fundamental results in game theory is that every finite strategic game has a Nash equilibrium, an assignment of (randomized) strategies to players with the stability property that no individual player can benefit from deviating from the assigned strategy. It is not known how to efficiently compute such a Nash equilibrium—the computational complexity of this task is characterized by the class PPAD, but the relation of PPAD to other problems and well-known complexity classes is not precisely understood. In recent years there has been mounting evidence, based on cryptographic tools and techniques, showing the hardness of PPAD. We continue this line of research by showing that PPAD is as hard as learning with errors (LWE) and the iterated squaring (IS) problem, two standard problems in cryptography. Our work improves over prior hardness results that relied either on (1) sub-exponential assumptions, or (2) relied on “obfustopia,” which can currently be based on a particular combination of three assumptions. Our work additionally establishes public-coin hardness for PPAD (computational hardness for a publicly sampleable distribution of instances) that seems out of reach of the obfustopia approach. Following the work of Choudhuri et al. (STOC 2019) and subsequent works, our hardness result is obtained by constructing an unambiguous and incrementally-updateable succinct non-interactive argument for IS, whose soundness relies on polynomial hardness of LWE. The result also implies a verifiable delay function with unique proofs, which may be of independent interest.
UR - http://www.scopus.com/inward/record.url?scp=85146717481&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85146717481&partnerID=8YFLogxK
U2 - 10.1007/978-3-031-22365-5_21
DO - 10.1007/978-3-031-22365-5_21
M3 - Conference contribution
AN - SCOPUS:85146717481
SN - 9783031223648
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 593
EP - 622
BT - Theory of Cryptography - 20th International Conference, TCC 2022, Proceedings
A2 - Kiltz, Eike
A2 - Vaikuntanathan, Vinod
PB - Springer Science and Business Media Deutschland GmbH
T2 - 20th Theory of Cryptography Conference, TCC 2022
Y2 - 7 November 2022 through 10 November 2022
ER -