Cryptology ePrint Archive: Report 2015/1078

Revisiting the Cryptographic Hardness of Finding a Nash Equilibrium

Sanjam Garg, Omkant Pandey, Akshayaram Srinivasan

Abstract: 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 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 {\em 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, polynomially hard computational assumption because constructions of \io\ inherently seems to require assumptions with sub-exponential hardness. In contrast, {\em 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 {\em 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.

Category / Keywords:

Original Publication (with minor differences): IACR-CRYPTO-2016

Date: received 5 Nov 2015, last revised 3 Jun 2016

Contact author: sanjamg at berkeley edu, omkant at gmail com, akshayaram at berkeley edu

Available format(s): PDF | BibTeX Citation

Version: 20160604:044836 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]