Revisiting the Cryptographic Hardness of Finding a Nash Equilibrium
Revisiting the Cryptographic Hardness of Finding a Nash Equilibrium
复制标题
重新审视寻找纳什均衡的密码学难度
DOI：
10.1007/978-3-662-53008-5_20
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Akshayaram Srinivasan
中科院分区：
文献类型：
--
作者：
Sanjam Garg;Omkant Pandey;Akshayaram Srinivasan
计算NASH平衡的确切硬度是算法游戏理论中的基本开放问题。对于复杂性类PPAD而言，此问题是完整的。众所周知，除非$ \ mathrm {np} = \ mathrm {conp} $$，否则PPAD中的问题不能为$$ \ mathrm {np} $ complete。因此，一个自然的方向是将PPAD的硬度降低到密码学中使用的问题的硬度。
Bitansky，Paneth和Rosen [Focs 2015]证明了PPAD的硬度，假设存在准真，难以区分的性混淆和亚指数上的硬性单向函数。这留下了将PPAD硬度基于更简单，多项式硬度，计算假设的可能性。
我们在这个方向上进一步进步，并将PPAD硬度直接降低到多项式硬性假设。假设存在多项式难以区分的混淆$$ i \ mathcal {o} $$和单向排列，我们的第一个结果证明了PPAD的硬度。尽管这对Bitansky等人的工作有所改善，但它并没有使我们减少更简单，多条件上的硬计算假设，因为$$ i \ Mathcal {o} $$的构造本质上似乎需要具有次指数硬度的假设。相反，公共密钥功能加密是一个简单得多的原始性，并且不会遭受此缺点。我们的第二个结果表明，$$ \ mathsf {ppad} $$硬度可以基于多项式紧凑的公共密钥功能加密和单向排列。我们的结果进一步证明了多项式紧凑的公共密钥功能加密的力量，这被认为比难以区分的混淆弱。我们的技术是一般的，我们希望它们具有各种应用。
The exact hardness of computing a Nash equilibrium is a fundamental open question in algorithmic game theory. This problem is complete for the complexity class PPAD. It is well known that problems in PPAD cannot be $$\mathrm {NP}$$ -complete unless $$\mathrm {NP}=\mathrm {coNP}$$ . Therefore, a natural direction is to reduce the hardness of PPAD to the hardness of problems used in cryptography.
Bitansky, Paneth, and Rosen [FOCS 2015] prove the hardness of PPAD assuming the existence of quasi-polynomially hard indistinguishability obfuscation and sub-exponentially hard one-way functions. This leaves open the possibility of basing PPAD hardness on simpler, polynomially hard, computational assumptions.
We make further progress in this direction and reduce PPAD hardness directly to polynomially hard assumptions. Our first result proves hardness of PPAD assuming the existence of polynomially hard indistinguishability obfuscation $$i\mathcal {O}$$ and one-way permutations. While this improves upon Bitansky et al.'s work, it does not give us a reduction to simpler, polynomially hard computational assumption because constructions of $$i\mathcal {O}$$ inherently seems to require assumptions with sub-exponential hardness. In contrast, public key functional encryption is a much simpler primitive and does not suffer from this drawback. Our second result shows that $$\mathsf{PPAD}$$ hardness can be based on polynomially hard compact public key functional encryption and one-way permutations. Our results further demonstrate the power of polynomially hard compact public key functional encryption which is believed to be weaker than indistinguishability obfuscation. Our techniques are general and we expect them to have various applications.