17
$\begingroup$

This question is inspired by the recent, beautiful work On the Cryptographic Hardness of Finding a Nash Equilibrium by Bitansky, Paneth, and Rosen.

Their main result is that the existence of indistinguishability obfuscation ($i\mathcal{O}$) and subexponentially-secure one-way functions implies that the $\mathsf{PPAD}$-complete search problem $\mathsf{End}$-$\mathsf{Of}$-$\mathsf{Line}$ (see for example, my old, old question) is worst-case hard for polynomial-time algorithms. Recall, of course, that the search problem of finding a Nash equilibrium in a normal form game of three or more players with specified utilities is (correct me if I'm wrong) known to be $\mathsf{PPAD}$-complete from a sequence of works beginning with the breakthrough of Daskalakis, Goldberg, and Papadimitriou. [Update: Finding two-player Nash equilibria is PPAD-complete -- Thanks Akshayaram Srinivasan for pointing this out.]

Independently, a (the?) major question in theoretical cryptography is to construct cryptographically-secure multilinear maps from $\underline{\rm standard}$ assumptions, in particular from the Learning with Errors ($\mathsf{LWE}$) assumption [Regev05]. (Any secure multilinear map, in turn, implies efficient indistinguishability obfuscation for $\mathsf{P/poly}$, landing us firmly far, far into the land of Cryptomania.)

However, this goal raises an interesting question: Suppose the Crypto community (sometime in the next year or few) jointly produces an appropriate reduction from the standard Learning with Errors assumption to the security of some indistinguishability obfuscation scheme for all circuits. Note that $\mathsf{LWE}$ is believed to be hard for quantum adversaries, formally by quantum reduction from approximating $\mathsf{GapSVP}$ to polynomial approximation ratios. In turn, $\mathsf{GapSVP}$ is "believed hard" for quantum computers itself, intuitively by $\mathsf{GapSVP}$'s "relation" to the Non-Abelian Hidden Subgroup Problem ($\mathsf{HSP}$) -- whereas Shor's algorithm solves the Abelian variant of $\mathsf{HSP}$. (If someone wants to independently fill me in more on the history/relationship between $\mathsf{GapSVP}$ and the Non-Abelian $\mathsf{HSP}$, great and thank you!)

The point is this: If indistinguishability obfuscation can be constructed for all circuits from $\mathsf{LWE}$ alone, then the resulting obfuscator will be quantum-secure. Intuitively, this seems to yield the following, simple and natural consequence of BPR's result/proof + the conjectured security of $i\mathcal{O}$ from $\mathsf{LWE}$ + the quantum-hardness of $\mathsf{LWE}$:


$\bullet$ Quantum computers cannot efficiently find Nash equilibria in the worst-case.


$\underline{\rm Question}:$ What, if any, consequence would the quantum hardness of finding Nash equilibria have? Is this an expected or unexpected outcome? Does anything overly weird occur, which we did not already observe simply from our implicit settling of $\mathsf{P}\ne\mathsf{NP}$ in order to allow a cryptographic assumption like $\mathsf{LWE}$ in the first place?

$\endgroup$
  • 2
    $\begingroup$ It's a great question. I don't know any interesting consequences of Nash equilibria not being in BQP, and it's possible nobody else does, either. But that doesn't mean it's not a good question. $\endgroup$ – Peter Shor Oct 31 '15 at 12:58
  • 1
    $\begingroup$ This is a fascinating question...I assume that you are interested in the relationship between BQP and PPAD. $\endgroup$ – Philip White Oct 31 '15 at 23:22
  • 1
    $\begingroup$ Of interest to people who care about this question: Here is some new follow-up work improving the quality of the BPR result. eprint.iacr.org/2015/1078.pdf --- PPAD-hardness follows from Compact functional encryption for circuits and One-way permutations, rather requiring than the full power of Indistinguishability obfuscation. (The main gain is that the requisite crypto primitives now require the more usual notion of security against poly-time attackers instead of security against subexp-time attackers.) $\endgroup$ – Daniel Apon Nov 6 '15 at 15:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.