Paper 2022/1272

PPAD is as Hard as LWE and Iterated Squaring

Nir Bitansky, Tel Aviv University
Arka Rai Choudhuri, University of California, Berkeley
Justin Holmgren, NTT Research
Chethan Kamath, Tel Aviv University
Alex Lombardi, Massachusetts Institute of Technology
Omer Paneth, Tel Aviv University
Ron D. Rothblum, Technion – Israel Institute of Technology
Abstract

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-updatable 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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A major revision of an IACR publication in TCC 2022
Contact author(s)
nirbitan @ tau ac il
arkarc @ berkeley edu
justin holmgren @ ntt-research com
ckamath @ protonmail com
alexlombardi @ alum mit edu
omerpa @ tauex tau ac il
rothblum @ cs technion ac il
History
2022-09-26: approved
2022-09-26: received
See all versions
Short URL
https://ia.cr/2022/1272
License
Creative Commons Attribution-ShareAlike
CC BY-SA

BibTeX

@misc{cryptoeprint:2022/1272,
      author = {Nir Bitansky and Arka Rai Choudhuri and Justin Holmgren and Chethan Kamath and Alex Lombardi and Omer Paneth and Ron D. Rothblum},
      title = {PPAD is as Hard as LWE and Iterated Squaring},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1272},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/1272}},
      url = {https://eprint.iacr.org/2022/1272}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.