CryptoDB
PPAD is as Hard as LWE and Iterated Squaring
| Authors: |
|
|---|---|
| Download: | |
| Presentation: | Slides |
| Conference: | TCC 2022 |
| Abstract: | One of the most fundamental results in game theory is that every 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* and the *iterated squaring* 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. |
BibTeX
@inproceedings{tcc-2022-32583,
title={PPAD is as Hard as LWE and Iterated Squaring},
publisher={Springer-Verlag},
author={Nir Bitansky and Arka Rai Choudhuri and Justin Holmgren and Chethan Kamath and Alex Lombardi and Omer Paneth and Ron D. Rothblum},
year=2022
}