Paper 2015/1078

Revisiting the Cryptographic Hardness of Finding a Nash Equilibrium

Sanjam Garg, Omkant Pandey, and 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.

Metadata
Available format(s)
PDF
Publication info
A minor revision of an IACR publication in CRYPTO 2016
Contact author(s)
sanjamg @ berkeley edu
omkant @ gmail com
akshayaram @ berkeley edu
History
2016-06-04: last of 2 revisions
2015-11-06: received
See all versions
Short URL
https://ia.cr/2015/1078
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/1078,
      author = {Sanjam Garg and Omkant Pandey and Akshayaram Srinivasan},
      title = {Revisiting the Cryptographic Hardness of Finding a Nash Equilibrium},
      howpublished = {Cryptology ePrint Archive, Paper 2015/1078},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/1078}},
      url = {https://eprint.iacr.org/2015/1078}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.