<p>This question is inspired by the recent, beautiful work On the Cryptographic Hardness of Finding a Nash Equilibrium by <a href="http://eccc.hpi-web.de/report/2015/001/" rel="nofollow noreferrer">Bitansky, Paneth, and Rosen</a>.</p>

<p>Their main result is that the existence of <a href="https://dash.harvard.edu/handle/1/12644697" rel="nofollow noreferrer">indistinguishability obfuscation</a> ($i\mathcal{O}$) and subexponentially-secure one-way functions implies that the <a href="https://complexityzoo.uwaterloo.ca/Complexity_Zoo:P#ppad" rel="nofollow noreferrer">$\mathsf{PPAD}$-complete</a> search problem $\mathsf{End}$-$\mathsf{Of}$-$\mathsf{Line}$ (see for example, my <a href="https://cstheory.stackexchange.com/questions/41/succinct-circuit-representation-of-graphs">old, old question</a>) 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 <a href="http://people.csail.mit.edu/costis/simplified.pdf" rel="nofollow noreferrer">Daskalakis, Goldberg, and Papadimitriou</a>. [Update: <a href="http://www.corelab.ece.ntua.gr/courses/gametheory/material/10.1.1.93.8285.pdf" rel="nofollow noreferrer">Finding <strong>two</strong>-player Nash equilibria is PPAD-complete</a> -- Thanks Akshayaram Srinivasan for pointing this out.]</p>

<p>Independently, a (the?) major question in theoretical cryptography is to construct cryptographically-secure <a href="https://eprint.iacr.org/2012/610.pdf" rel="nofollow noreferrer">multilinear maps</a> from $\underline{\rm standard}$ assumptions, in particular from the Learning with Errors ($\mathsf{LWE}$) assumption [<a href="http://www.cims.nyu.edu/~regev/papers/qcrypto.pdf" rel="nofollow noreferrer">Regev05</a>]. (Any secure multilinear map, in turn, implies efficient indistinguishability obfuscation for $\mathsf{P/poly}$, landing us <strong>firmly</strong> far, far into the land of <a href="http://blog.computationalcomplexity.org/2004/06/impagliazzos-five-worlds.html" rel="nofollow noreferrer">Cryptomania</a>.)</p>

<p>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 <em>hard for quantum adversaries</em>, formally by <em>quantum</em> 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 <a href="http://arxiv.org/abs/quant-ph/9508027" rel="nofollow noreferrer">Shor's algorithm</a> solves the <em>Abelian</em> 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!)</p>

<p>The point is this: If indistinguishability obfuscation can be constructed for all circuits from $\mathsf{LWE}$ <strong>alone</strong>, then the resulting obfuscator will be <strong>quantum-secure</strong>. 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}$:</p>

<hr>

<p>$\bullet$ <strong>Quantum computers cannot efficiently find Nash equilibria in the worst-case.</strong></p>

<hr>

<p>$\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?</p>

CC BY-SA 3.0
2015-10-31T12:58:18.177Z
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.
Peter Shor 
CC BY-SA 3.0
2015-11-06T15:41:31.863Z
Of interest to people who care about this question: Here is some new follow-up work improving the quality of the BPR result. http://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.)
Daniel Apon
<cc.complexity-theory><quantum-computing><cr.crypto-security><gt.game-theory><conditional-results>
Quantum Hardness of Finding Nash Equilibria
Daniel Apon
# Quantum Hardness of Finding Nash Equilibria

(Asked by: username_0 on 2015-10-30)

This question is inspired by the recent, beautiful work On the Cryptographic Hardness of Finding a Nash Equilibrium by [Bitansky, Paneth, and Rosen](http://eccc.hpi-web.de/report/2015/001/).

Their main result is that the existence of [indistinguishability obfuscation](https://dash.harvard.edu/handle/1/12644697) ($i\mathcal{O}$) and subexponentially-secure one-way functions implies that the [$\mathsf{PPAD}$-complete](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:P#ppad) search problem $\mathsf{End}$-$\mathsf{Of}$-$\mathsf{Line}$ (see for example, my [old, old question](https://cstheory.stackexchange.com/questions/41/succinct-circuit-representation-of-graphs)) 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](http://people.csail.mit.edu/costis/simplified.pdf). [Update: [Finding **two**-player Nash equilibria is PPAD-complete](http://www.corelab.ece.ntua.gr/courses/gametheory/material/10.1.1.93.8285.pdf) -- Thanks Akshayaram Srinivasan for pointing this out.]

Independently, a (the?) major question in theoretical cryptography is to construct cryptographically-secure [multilinear maps](https://eprint.iacr.org/2012/610.pdf) from $\underline{\rm standard}$ assumptions, in particular from the Learning with Errors ($\mathsf{LWE}$) assumption [[Regev05](http://www.cims.nyu.edu/~regev/papers/qcrypto.pdf)]. (Any secure multilinear map, in turn, implies efficient indistinguishability obfuscation for $\mathsf{P/poly}$, landing us **firmly** far, far into the land of [Cryptomania](http://blog.computationalcomplexity.org/2004/06/impagliazzos-five-worlds.html).)

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](http://arxiv.org/abs/quant-ph/9508027) 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?

**Tags:** cc.complexity-theory, quantum-computing, cr.crypto-security, gt.game-theory, conditional-results

> **Comments:**
> **username_1**: 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.  
> **username_0**: Of interest to people who care about this question: Here is some new follow-up work improving the quality of the BPR result. http://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.)  

---

## 0 answers

