PPAD is as Hard as LWE and Iterated Squaring
PPAD is as Hard as LWE and Iterated Squaring
复制标题
PPAD 与 LWE 和迭代平方一样困难
DOI：
--
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Ron D. Rothblum
中科院分区：
文献类型：
--
作者：
Nir Bitansky;A. Choudhuri;Justin Holmgren;Chethan Kamath;Alex Lombardi;Omer Paneth;Ron D. Rothblum
博弈论中最基本的结果之一是，每个有限策略博弈都有一个纳什均衡，一个分配给玩家的（随机）策略的稳定性属性，没有单个玩家可以从偏离分配的策略中受益。目前还不知道如何有效地计算这样一个纳什均衡-这个任务的计算复杂性的特点是类PPAD，但PPAD的关系，其他问题和众所周知的复杂性类是不准确的理解。近年来，基于密码工具和技术的越来越多的证据表明PPAD的硬度。我们继续这条线的研究表明，PPAD是很难学习错误（LWE）和迭代平方（IS）的问题，在密码学的两个标准问题。我们的工作改进了先前的硬度结果，这些结果依赖于（1）次指数假设，或（2）依赖于“obfustopia”，目前可以基于三个假设的特定组合。我们的工作还为PPAD（实例的公共采样分布的计算硬度）建立了公共硬币硬度，这似乎超出了obfustopia方法的范围。在Choudhuri等人的工作之后。（STOC 2019）和后续工作，我们的硬度结果是通过为IS构建一个明确的和可增量更新的简洁的非交互式参数来获得的，其可靠性依赖于LWE的多项式硬度。结果还暗示了一个可验证的延迟函数，具有唯一的证明，这可能是独立的利益。特拉维夫大学。电子邮件：nirbitan@tau.ac.il，ckamath@protonmail.com，omerpa@tauex.tau.ac.il †加州大学伯克利分校。电子邮件：arkarc@berkeley.edu电子邮件：justin. ntt-research.com §MIT。电子邮件：alexlombardi@alum.mit.edu ¶Technion.电子邮件地址：rothblum@cs.technion.ac.il
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 wellknown 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 noninteractive 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. ∗Tel Aviv University. Email: nirbitan@tau.ac.il, ckamath@protonmail.com, omerpa@tauex.tau.ac.il †UC Berkeley. Email: arkarc@berkeley.edu ‡NTT Research. Email: justin.holmgren@ntt-research.com §MIT. Email: alexlombardi@alum.mit.edu ¶Technion. Email: rothblum@cs.technion.ac.il
势线的独特末端
影响因子：
--
作者：
Fearnley, John;Gordon, Spencer;Mehta, Ruta;Savani, Rahul
通讯作者：
Savani, Rahul
LWE 的可并行委托
DOI：
--
发表时间：
2022
期刊：
TCC'22
影响因子：
--
作者：
Cody Freitag, Rafael Pass
通讯作者：
Cody Freitag, Rafael Pass