On the Exact Cryptographic Hardness of Finding a Nash Equilibrium.
Sanjam Garg, Omkant Pandey, Akshayaram Srinivasan · 2015
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 NP-complete unless NP = 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 ex-istence of quasi-polynomially hard indistinguishability obfuscation and sub-exponentially hard one-way functions. This leaves open the possibility of basing PPAD hardness on simpler, poly-nomially hard, computational assumptions. We make further progress in this direction and reduce PPAD hardness directly to polyno-mially hard assumptions. Our first result proves hardness of PPAD assuming the existence of polynomially hard indistinguishability obfuscation (iO) and one-way permutations. While this improves upon Bitansky et al.’s work, it does not give us a reduction to simpler, polynomi-ally hard computational assumption because constructions of iO 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 PPAD hardness can be based on polynomially hard public key functional encryption and one-way permutations. Our results further demonstrate the power of polynomially hard public key functional encryption which is believed to be weaker than indistinguishability obfuscation.