<p>Two answers that I learnt while writing a <a href="https://theorydish.blog/2018/06/26/will-quantum-communication-make-us-more-cooperative/" rel="noreferrer">blog post</a> about this question </p>

<ol>
<li><p><strong>No</strong>: In black-box variants, quantum query/communication complexity offer the Grover quadratic speedup, but not more than that. As Ron points out, this extends to computational complexity under plausible assumptions.</p></li>
<li><p><strong>Maybe</strong>: Nash equilibrium is arguably the flagship problem of "Christos classes". Here, giving players access to quantum entanglement suggests a new solution concept of "quantum correlated equilibrium" which generalizes Nash equilibrium. Its complexity is still open. See <a href="https://arxiv.org/abs/1101.3380" rel="noreferrer">this cool paper</a> by Alan Deckelbaum.</p></li>
</ol>

<p>And one historical note: PLS was actually introduced by <a href="https://www-sciencedirect-com.stanford.idm.oclc.org/science/article/pii/0022000088900463" rel="noreferrer">Johnson-Papadimitriou-Yannakakis in 1988</a>.</p>

CC BY-SA 4.0
2019-09-09T07:07:19.840Z
Many thanks, Aviad! And welcome to the site!
Gil Kalai
CC BY-SA 4.0
2019-09-11T08:55:14.267Z
I still dont understand 1. Certainly there are cryptographic hardness assumptions which do not apply in the quantum case. What is it that makes "breaking Fiat-Shamir" hard for QC unlike, say "breaking RSA".
Gil Kalai
CC BY-SA 4.0
2019-09-09T07:01:22.573Z
2019-09-09T07:01:22.573Z
Aviad Rubinstein
<p>I will attempt to elaborate a bit on why <a href="https://eprint.iacr.org/2019/549.pdf" rel="nofollow noreferrer">CHKPRR</a> shows that <span class="math-container">$\mathsf{PPAD}$</span> is plausibly hard for quantum computers.</p>
<p>At a high level, CHKPRR builds a distribution over end-of-line instances where finding a solution requires to either:</p>
<ul>
<li>break the soundness of the proof system obtained by applying the Fiat-Shamir heuristic to the famous sumcheck protocol, or</li>
<li>solving a <span class="math-container">$\sharp \mathsf{P}$</span>-complete problem</li>
</ul>
<p>Intuitively, the reduction starts from a <span class="math-container">$\sharp \mathsf{SAT}$</span> instance. Counting requires an exponential number of polynomial steps; the authors make this counting <em>incrementally verifiable</em> by letting the counting procedure maintain a state, updated after every step, which proves the correctness of the computation so far. This incrementally verifiable counting procedure is then used to build an instance of the relaxed sink-of-verifiable-line problem, a promise problem which can be reduced to total search problems in <span class="math-container">$\mathsf{PPAD}$</span>.</p>
<p>To instantiate this idea, the main technical challenge is to come up with a way to make the counting incrementally verifiable: we need a short, <em>non-interactive</em> proof at each step of the computation, which demonstrates correctness of the computation so far. Here, non-interactivity is the core issue; indeed we already know of a short <em>interactive</em> proof for demonstrating statements of the form <span class="math-container">$\sum_{\vec z \in \{0,1\}^n} f(\vec z) = x$</span>, where <span class="math-container">$f$</span> is some low-degree <span class="math-container">$n$</span>-variate polynomial over a field <span class="math-container">$\mathbb{F}$</span>, which would work perfectly fine in this setting: the <a href="https://pdfs.semanticscholar.org/a87d/3febd2e02c41a9b0a4e423089b6677eaef3b.pdf" rel="nofollow noreferrer">sumcheck protocol</a>. Converting an interactive proof into a non-interactive one (maintaining public verifiability and compactness) is exactly what the Fiat-Shamir heuristic does.</p>
<p><strong>Instantiating Fiat-Shamir</strong></p>
<p>The Fiat-Shamir heuristic is very simple: fix some hash function, start with a public-coin interactive proof, and replace each random message of the verifier by a hash of the entire transcript so far. The question is then under which property of the hash function we can prove that the resulting protocol is still sound (note that it cannot be statistically sound anymore; the hope is that it remains computationally sound).</p>
<p>Before I elaborate on this, let me address your comment:</p>
<blockquote>
<p>I still dont understand 1. Certainly there are cryptographic hardness assumptions which do not apply in the quantum case. What is it that makes &quot;breaking Fiat-Shamir&quot; hard for QC unlike, say &quot;breaking RSA&quot;.</p>
</blockquote>
<p>The high level description I gave should make it clear, I hope, that &quot;breaking Fiat-Shamir&quot; and &quot;breaking RSA&quot; are not really comparable problems. RSA is a concrete, specific hardness assumption, and if you can factor large integers, then you can break it.</p>
<p>On the other hand, the conjectured hardness of breaking Fiat-Shamir is a much more generic assumption. When you <em>instantiate</em> the Fiat-Shamir heuristic, you pick a concrete choice of hash function; but it suffices for the <span class="math-container">$\mathsf{PPAD}$</span>-hardness result of CHKPRR that there <em>exists</em> some hash function for which Fiat-Shamir is sound. Breaking Fiat-Shamir with a quantum computer would require showing an attack against its soundness for <em>any possible choice</em> of the underlying hash function. At an intuitive level, this is not what quantum computers are good at, because this is a problem that does not seem to necessarily have a strong structure which it could exploit (unlike, e.g., discrete logarithm and RSA): hash functions can be typically very &quot;unstructured&quot;.</p>
<p>In more concrete terms, there are two natural alternatives when picking a hash function to instantiate Fiat-Shamir:</p>
<p><strong>The heuristic, concretely efficient approach:</strong></p>
<p>pick your favorite hash function, say, SHA-3. We have of course no proof that instantiating Fiat-Shamir with SHA-3 gives us a hard problem; but neither do we know of any non-trivial attack on the soundness of proof systems obtained by applying Fiat-Shamir with SHA-3 to a non-degenerate interactive proof system. This extends to the quantum setting as well: we do not know of any quantum attack that does better than the usual quadratic speedup given by Grover's algorithm. After decades of cryptanalysis attempts, the consensus in the cryptographic community is that quantum algorithm do not <em>seem</em>, as far as we can see, to provide superpolynomial speedups for &quot;Minicrypt-style&quot; primitives (hash functions, PRGs, block ciphers, etc) without some strong underlying algebraic structure - such as SHA-2, SHA-3, AES, etc.</p>
<p><strong>The provable security approach:</strong></p>
<p>here the goal is to isolate a clean property of the hash function that makes the Fiat-Shamir heuristic sound, and to build a hash function which satisfies this properties under plausible cryptographic assumptions.</p>
<p>This provable security approach has a long and dense history in crypto. Among the most promising candidates is the notion of <em>correlation-intractable hash functions</em>: a (keyed) hash function is said to be <em>correlation-intractable</em> with respect to some relation <span class="math-container">$R$</span> if it is computationally infeasible, given a random hash key <span class="math-container">$K$</span>, to find an input <span class="math-container">$x$</span> such that <span class="math-container">$(x, H_K(x)) \in R$</span>. Intuitively, this captures what we want from Fiat-Shamir in a natural way: in an interactive proof system, where soundness is statistical, there exists some &quot;bad verifier messages&quot; which are very unlikely, but which would allow the prover to cheat. What we want is that the prover cannot compute a transcript such that, when computing the verifier's next message by hashing it, he manages to find one of those &quot;bad messages&quot;. Any interactive proof system is therefore associated to some sparse relation <span class="math-container">$R$</span> that contains the pairs (transcript, bad message for this transcript), and Fiat-Shamir is sound when instantiated with a hash function which is correlation-intractable for this sparse relation <span class="math-container">$R$</span>.</p>
<p>The question is now how to build correlation-intractable hash functions for relations we care about - and in this specific context, for the relation associated to the sumcheck protocol. Here, a recent line of work (essentially <a href="https://eprint.iacr.org/2015/334.pdf" rel="nofollow noreferrer">1</a>,<a href="https://eprint.iacr.org/2018/385.pdf" rel="nofollow noreferrer">2</a>,<a href="https://eprint.iacr.org/2018/131.pdf" rel="nofollow noreferrer">3</a>,<a href="https://eprint.iacr.org/2018/1004.pdf" rel="nofollow noreferrer">4</a>,<a href="https://eprint.iacr.org/2018/1248.pdf" rel="nofollow noreferrer">5</a>,<a href="https://eprint.iacr.org/2019/158.pdf" rel="nofollow noreferrer">6</a>) has shown that, for many relations of interest, one can actually build correlation intractable hash functions under lattice-based assumptions.</p>
<p>Lattice-based cryptography is cryptographers' current best bet for building quantum-safe cryptographic primitives. For most problems over lattices considered by the crypto community, no better quantum algorithm is known than the usual &quot;classical algorithm + Grover quadratic speedup&quot;. So, if we could base a correlation-intractable hash function for the sumcheck relation on a well-established lattice assumption, this would be seen in the crypto community as a very strong indication that quantum computers cannot always break Fiat-Shamir (hence, cannot solve <span class="math-container">$\mathsf{PPAD}$</span>).</p>
<p>We are not exactly there, in fact. The recent breakthrough result of Peikert and Shiehian (the last paper in the list I gave previously) showed that for important relations, we can build correlation-intractable hash function under well-established lattice problems, such as learning with error, or the SIS problem; however, the sumcheck relation is not captured by this work.</p>
<p>Still, CHKPRR, building on <a href="https://eprint.iacr.org/2018/1004.pdf" rel="nofollow noreferrer">this work</a> showed that one can build a correlation-intractable hash function under the assumption that any of many concrete constructions of fully-homomorphic encryption schemes has quasi-optimal circular security against superpolynomial time attacks.</p>
<p>Let's break down this assumption:</p>
<ul>
<li>Fully homomorphic encryption (FHE) is a primitive which we know how to build under a variety of lattice assumptions. If the scheme must only evaluate bounded size circuits, we know in fact how to build it under the standard learning with error assumption.</li>
<li>Circular security states that the FHE should be hard to break even when it is used to encrypt its own secret key. This is stronger than the usual security notion, which does not allow key dependent messages. It is a major and long standing open problem to build a circularly-secure FHE under a standard lattice assumption, such as LWE. Still, a decade after Gentry's first FHE construction and a lot of cryptanalysis attempts, the circular security of established FHE candidates has itself become a relatively safe-looking assumption (even against quantum computers), and we do not know of any attack that exploits key-dependent encryptions in a nontrivial way.</li>
<li>quasi-optimal hardness means that all polynomial algorithms have exponentially low probability of breaking the scheme (i.e., probability <span class="math-container">$2^{\omega(\log \lambda) - \lambda}$</span>, where <span class="math-container">$\lambda$</span> is the security parameter). Note that while we might know non-trivial exponential time algorithms, that would break the scheme with non-negligible probability in time <span class="math-container">$2^{c\lambda}$</span> for some <span class="math-container">$c &lt; 1$</span>, we do not know of any <em>polynomial time</em> algorithm that breaks the scheme with a probability <span class="math-container">$2^{-c \lambda}$</span> for some <span class="math-container">$c &lt; 1$</span>.</li>
<li>Finally, we want all the above to still hold if we allow superpolynomial running time to the attacker. This is still in line with what known algorithms can achieve.</li>
</ul>
<p>All in all, this is clearly not a great, highly plausible and well-established assumption. However, it creates a very interesting connection: it connects the hardness of solving <span class="math-container">$\mathsf{PPAD}$</span> with a quantum computer to the question of obtaining strong nontrivial improvements over the best known quantum algorithms to attack important lattice-based cryptographic primitives (fully homomorphic encryption), which is a well-investigated question.</p>
<p>Of course, one of the main open questions left by CHKPRR is to build a correlation-intractable hash function for the sumcheck relation under a better lattice-based assumption - ideally, the LWE assumption. This seems non-trivial, but not implausible, given that this is a very recent line of work, where many surprising results have already been achieved for other interesting relations.</p>
<p><strong>EDIT</strong></p>
<p>Apparently, the above result has just been improved in <a href="https://eprint.iacr.org/2020/860.pdf" rel="nofollow noreferrer">this paper</a> to rely solely on the subexponential hardness of LWE (together with the average case hardness of <span class="math-container">$\#$</span>SAT). This is a major and impressive improvement (not yet peer reviewed, but from very strong researchers, hence very believable) which provides very strong support (essentially as strong as we could hope for using well-studied cryptographic assumptions) for the hypothesis that PPAD is beyond the power of quantum computers.</p>

CC BY-SA 4.0
2019-09-12T14:56:17.427Z
Dear Geoffroy, very many thanks for your great answer!
Gil Kalai
CC BY-SA 4.0
2020-07-16T21:31:50.960Z
You are welcome. I just edited by answer to mention a very recent result that shows PPAD hardness under a much, much better assumption, the subexponential hardness of LWE, which is widely believed to hold against quantum computers. This essentially resolves the main open problem from the paper I discussed in my answer, of basing PPAD hardness on some of the most well-studied plausibly quantum-secure cryptographic assumption (the previous paper was more of a win-win result, showing that quantum attacks on PPAD hardness would provide non-trivial speedups for attacking important crypto schemes).
Geoffroy Couteau
CC BY-SA 4.0
2019-09-12T11:54:51.247Z
2020-07-16T21:29:07.280Z
2020-07-16T21:29:07.280Z
Geoffroy Couteau
<p>Today <a href="http://papafest.cs.columbia.edu/" rel="noreferrer">in New York</a> and all over the world Christos Papadimitriou's birthday is celebrated. This is a good opportunity to ask about the relations between Christos' complexity class PPAD (and his other related classes) and quantum computers. In his <a href="https://people.eecs.berkeley.edu/~christos/papers/On%20the%20Complexity.pdf" rel="noreferrer">celebrated 1994 paper</a> Papadimitriou introduced and systematically studied several important complexity classes like PLS, PPAD and others.  (Papadimitriou's paper relied on some earlier papers and, in particular, as Aviad noted, PLS was introduced by Johnson-Papadimitriou-Yannakakis in 1988.)</p>

<p>My main question is: </p>

<blockquote>
  <p>Do quantum computers give some advantage for problems in <span class="math-container">$PPAD$</span>? or in
  <span class="math-container">$PLS$</span>? or in <span class="math-container">$PLS \cap PPAD$</span>? etc...</p>
</blockquote>

<p>Another question is if there is some quantum analogs of PLS and PPAD and Christos' other classes.</p>

<p>I note that a recent remarkable connections of PPAD to cryptography was found in these papers: <a href="https://link.springer.com/chapter/10.1007/978-3-319-70503-3_25" rel="noreferrer">On the cryptographic hardness of finding a Nash equilibrium</a>‏ by N Bitansky, O Paneth, A Rosen and <a href="https://link.springer.com/chapter/10.1007/978-3-319-70503-3_25" rel="noreferrer">Can PPAD hardness be based on standard cryptographic assumptions?</a> by A Rosen, G Segev, I Shahaf, and <a href="https://eccc.weizmann.ac.il/report/2019/074/?fbclid=IwAR2-vKJ6AOgNg8SzEK-LoN9Ag0GgpaTp1QwXtmy-_fayzQ0HLkD_9hqdHIk" rel="noreferrer">Finding a Nash Equilibrium Is No Easier Than Breaking Fiat-Shamir</a> by Arka Rai Choudhuri, Pavel Hubacek, Chethan Kamath, Krzysztof Pietrzak, Alon Rosen, Guy Rothblum.  I also note that in my opinion Christos' classes are especially close to mathematics and mathematical proofs. </p>

<p><strong>Update:</strong> Ron Rothblum commented (over FB) that the Choudhuri, Hubacek, Kamath, Pietrzak, Rosen, and G. Rothblum's results implies that PPAD is plausibly beyond the power of quantum computers. (I will be happy to see an elaborated answer explaining it.)</p>

<p>One more comment: A related nice question is if finding the sink in a unique singe orientation of the <span class="math-container">$n$</span>-cube has an efficient quantum algorithm. (I think this task is easier than <span class="math-container">$PLS$</span> but I am not sure how it is related to <span class="math-container">$PPAD$</span>.) This is related to the quest to find quantum advantage for <span class="math-container">$LP$</span> see <a href="https://cstheory.stackexchange.com/a/767/712">https://cstheory.stackexchange.com/a/767/712</a> .  </p>

<p><a href="https://i.sstatic.net/qE50X.png" rel="noreferrer"><img src="https://i.sstatic.net/qE50X.png" alt="enter image description here"></a>
Happy birthday, Christos!</p>

CC BY-SA 4.0
2020-02-14T13:51:36.673Z
Regarding Unique-Sink-Orientation (USO), it was [recently shown](https://arxiv.org/abs/1811.03841v1) to reduce to a problem called Unique-End-Of-Potential-Line, which is (polynomially-equivalent) to End-of-Metered-Line (EOML). Both these problems lie in a class [$CLS\subseteq PLS\cap PPAD$](https://en.wikipedia.org/wiki/TFNP#CLS) which is, loosely-speaking, a "smooth" counterpart of PLS. The CHKPRR results also show how to build hard instances of EOML, and therefore CLS. However since it is not known if EOML reduces to USO, it could still be the case that USO is easy for quantum computers.
ckamath
CC BY-SA 4.0
2020-02-14T13:59:51.740Z
Dear @Occams_Trimmer, is there reason to think that USO is hard for classical computers? E.g. is it complete for some of the classes you mentioned?
Gil Kalai
CC BY-SA 4.0
2020-02-14T14:04:32.877Z
No, it is not known to be complete for any class (as far as I know). Since USO is quite low in the hierarchy, it is plausible that it is easy in the classical case too.
ckamath
<cc.complexity-theory><complexity-classes><quantum-computing><cr.crypto-security><nash-equilibrium>
PPAD and Quantum
Gil Kalai
# PPAD and Quantum

(Asked by: username_0 on 2019-09-08)

Today [in New York](http://papafest.cs.columbia.edu/) and all over the world Christos Papadimitriou's birthday is celebrated. This is a good opportunity to ask about the relations between Christos' complexity class PPAD (and his other related classes) and quantum computers. In his [celebrated 1994 paper](https://people.eecs.berkeley.edu/~christos/papers/On%20the%20Complexity.pdf) Papadimitriou introduced and systematically studied several important complexity classes like PLS, PPAD and others. (Papadimitriou's paper relied on some earlier papers and, in particular, as Aviad noted, PLS was introduced by Johnson-Papadimitriou-Yannakakis in 1988.)

My main question is:

> Do quantum computers give some advantage for problems in $PPAD$? or in
> $PLS$? or in $PLS \cap PPAD$? etc...

Another question is if there is some quantum analogs of PLS and PPAD and Christos' other classes.

I note that a recent remarkable connections of PPAD to cryptography was found in these papers: [On the cryptographic hardness of finding a Nash equilibrium](https://link.springer.com/chapter/10.1007/978-3-319-70503-3_25)‏ by N Bitansky, O Paneth, A Rosen and [Can PPAD hardness be based on standard cryptographic assumptions?](https://link.springer.com/chapter/10.1007/978-3-319-70503-3_25) by A Rosen, G Segev, I Shahaf, and [Finding a Nash Equilibrium Is No Easier Than Breaking Fiat-Shamir](https://eccc.weizmann.ac.il/report/2019/074/?fbclid=IwAR2-vKJ6AOgNg8SzEK-LoN9Ag0GgpaTp1QwXtmy-_fayzQ0HLkD_9hqdHIk) by Arka Rai Choudhuri, Pavel Hubacek, Chethan Kamath, Krzysztof Pietrzak, Alon Rosen, Guy Rothblum. I also note that in my opinion Christos' classes are especially close to mathematics and mathematical proofs.

**Update:** Ron Rothblum commented (over FB) that the Choudhuri, Hubacek, Kamath, Pietrzak, Rosen, and G. Rothblum's results implies that PPAD is plausibly beyond the power of quantum computers. (I will be happy to see an elaborated answer explaining it.)

One more comment: A related nice question is if finding the sink in a unique singe orientation of the $n$-cube has an efficient quantum algorithm. (I think this task is easier than $PLS$ but I am not sure how it is related to $PPAD$.) This is related to the quest to find quantum advantage for $LP$ see <https://cstheory.stackexchange.com/a/767/712> .

[![enter image description here](https://i.sstatic.net/qE50X.png)](https://i.sstatic.net/qE50X.png)
Happy birthday, Christos!

**Tags:** cc.complexity-theory, complexity-classes, quantum-computing, cr.crypto-security, nash-equilibrium
> **Comments:**
> **username_1**: Regarding Unique-Sink-Orientation (USO), it was [recently shown](https://arxiv.org/abs/1811.03841v1) to reduce to a problem called Unique-End-Of-Potential-Line, which is (polynomially-equivalent) to End-of-Metered-Line (EOML). Both these problems lie in a class [$CLS\subseteq PLS\cap PPAD$](https://en.wikipedia.org/wiki/TFNP#CLS) which is, loosely-speaking, a "smooth" counterpart of PLS. The CHKPRR results also show how to build hard instances of EOML, and therefore CLS. However since it is not known if EOML reduces to USO, it could still be the case that USO is easy for quantum computers.  
> **username_0**: Dear @Occams_Trimmer, is there reason to think that USO is hard for classical computers? E.g. is it complete for some of the classes you mentioned?  
> **username_1**: No, it is not known to be complete for any class (as far as I know). Since USO is quite low in the hierarchy, it is plausible that it is easy in the classical case too.  

---

## 2 answers

### Answer by username_2 on 2019-09-09. Score: 11

Two answers that I learnt while writing a [blog post](https://theorydish.blog/2018/06/26/will-quantum-communication-make-us-more-cooperative/) about this question

1. **No**: In black-box variants, quantum query/communication complexity offer the Grover quadratic speedup, but not more than that. As Ron points out, this extends to computational complexity under plausible assumptions.
2. **Maybe**: Nash equilibrium is arguably the flagship problem of "Christos classes". Here, giving players access to quantum entanglement suggests a new solution concept of "quantum correlated equilibrium" which generalizes Nash equilibrium. Its complexity is still open. See [this cool paper](https://arxiv.org/abs/1101.3380) by Alan Deckelbaum.

And one historical note: PLS was actually introduced by [Johnson-Papadimitriou-Yannakakis in 1988](https://www-sciencedirect-com.stanford.idm.oclc.org/science/article/pii/0022000088900463).

> **Comments:**
> **username_0**: Many thanks, Aviad! And welcome to the site!  
> **username_0**: I still dont understand 1. Certainly there are cryptographic hardness assumptions which do not apply in the quantum case. What is it that makes "breaking Fiat-Shamir" hard for QC unlike, say "breaking RSA".  

---

### Answer by username_3 on 2019-09-12. Score: 9

I will attempt to elaborate a bit on why [CHKPRR](https://eprint.iacr.org/2019/549.pdf) shows that $\mathsf{PPAD}$ is plausibly hard for quantum computers.

At a high level, CHKPRR builds a distribution over end-of-line instances where finding a solution requires to either:

* break the soundness of the proof system obtained by applying the Fiat-Shamir heuristic to the famous sumcheck protocol, or
* solving a $\sharp \mathsf{P}$-complete problem

Intuitively, the reduction starts from a $\sharp \mathsf{SAT}$ instance. Counting requires an exponential number of polynomial steps; the authors make this counting *incrementally verifiable* by letting the counting procedure maintain a state, updated after every step, which proves the correctness of the computation so far. This incrementally verifiable counting procedure is then used to build an instance of the relaxed sink-of-verifiable-line problem, a promise problem which can be reduced to total search problems in $\mathsf{PPAD}$.

To instantiate this idea, the main technical challenge is to come up with a way to make the counting incrementally verifiable: we need a short, *non-interactive* proof at each step of the computation, which demonstrates correctness of the computation so far. Here, non-interactivity is the core issue; indeed we already know of a short *interactive* proof for demonstrating statements of the form $\sum\_{\vec z \in \{0,1\}^n} f(\vec z) = x$, where $f$ is some low-degree $n$-variate polynomial over a field $\mathbb{F}$, which would work perfectly fine in this setting: the [sumcheck protocol](https://pdfs.semanticscholar.org/a87d/3febd2e02c41a9b0a4e423089b6677eaef3b.pdf). Converting an interactive proof into a non-interactive one (maintaining public verifiability and compactness) is exactly what the Fiat-Shamir heuristic does.

**Instantiating Fiat-Shamir**

The Fiat-Shamir heuristic is very simple: fix some hash function, start with a public-coin interactive proof, and replace each random message of the verifier by a hash of the entire transcript so far. The question is then under which property of the hash function we can prove that the resulting protocol is still sound (note that it cannot be statistically sound anymore; the hope is that it remains computationally sound).

Before I elaborate on this, let me address your comment:

> I still dont understand 1. Certainly there are cryptographic hardness assumptions which do not apply in the quantum case. What is it that makes "breaking Fiat-Shamir" hard for QC unlike, say "breaking RSA".

The high level description I gave should make it clear, I hope, that "breaking Fiat-Shamir" and "breaking RSA" are not really comparable problems. RSA is a concrete, specific hardness assumption, and if you can factor large integers, then you can break it.

On the other hand, the conjectured hardness of breaking Fiat-Shamir is a much more generic assumption. When you *instantiate* the Fiat-Shamir heuristic, you pick a concrete choice of hash function; but it suffices for the $\mathsf{PPAD}$-hardness result of CHKPRR that there *exists* some hash function for which Fiat-Shamir is sound. Breaking Fiat-Shamir with a quantum computer would require showing an attack against its soundness for *any possible choice* of the underlying hash function. At an intuitive level, this is not what quantum computers are good at, because this is a problem that does not seem to necessarily have a strong structure which it could exploit (unlike, e.g., discrete logarithm and RSA): hash functions can be typically very "unstructured".

In more concrete terms, there are two natural alternatives when picking a hash function to instantiate Fiat-Shamir:

**The heuristic, concretely efficient approach:**

pick your favorite hash function, say, SHA-3. We have of course no proof that instantiating Fiat-Shamir with SHA-3 gives us a hard problem; but neither do we know of any non-trivial attack on the soundness of proof systems obtained by applying Fiat-Shamir with SHA-3 to a non-degenerate interactive proof system. This extends to the quantum setting as well: we do not know of any quantum attack that does better than the usual quadratic speedup given by Grover's algorithm. After decades of cryptanalysis attempts, the consensus in the cryptographic community is that quantum algorithm do not *seem*, as far as we can see, to provide superpolynomial speedups for "Minicrypt-style" primitives (hash functions, PRGs, block ciphers, etc) without some strong underlying algebraic structure - such as SHA-2, SHA-3, AES, etc.

**The provable security approach:**

here the goal is to isolate a clean property of the hash function that makes the Fiat-Shamir heuristic sound, and to build a hash function which satisfies this properties under plausible cryptographic assumptions.

This provable security approach has a long and dense history in crypto. Among the most promising candidates is the notion of *correlation-intractable hash functions*: a (keyed) hash function is said to be *correlation-intractable* with respect to some relation $R$ if it is computationally infeasible, given a random hash key $K$, to find an input $x$ such that $(x, H\_K(x)) \in R$. Intuitively, this captures what we want from Fiat-Shamir in a natural way: in an interactive proof system, where soundness is statistical, there exists some "bad verifier messages" which are very unlikely, but which would allow the prover to cheat. What we want is that the prover cannot compute a transcript such that, when computing the verifier's next message by hashing it, he manages to find one of those "bad messages". Any interactive proof system is therefore associated to some sparse relation $R$ that contains the pairs (transcript, bad message for this transcript), and Fiat-Shamir is sound when instantiated with a hash function which is correlation-intractable for this sparse relation $R$.

The question is now how to build correlation-intractable hash functions for relations we care about - and in this specific context, for the relation associated to the sumcheck protocol. Here, a recent line of work (essentially [1](https://eprint.iacr.org/2015/334.pdf),[2](https://eprint.iacr.org/2018/385.pdf),[3](https://eprint.iacr.org/2018/131.pdf),[4](https://eprint.iacr.org/2018/1004.pdf),[5](https://eprint.iacr.org/2018/1248.pdf),[6](https://eprint.iacr.org/2019/158.pdf)) has shown that, for many relations of interest, one can actually build correlation intractable hash functions under lattice-based assumptions.

Lattice-based cryptography is cryptographers' current best bet for building quantum-safe cryptographic primitives. For most problems over lattices considered by the crypto community, no better quantum algorithm is known than the usual "classical algorithm + Grover quadratic speedup". So, if we could base a correlation-intractable hash function for the sumcheck relation on a well-established lattice assumption, this would be seen in the crypto community as a very strong indication that quantum computers cannot always break Fiat-Shamir (hence, cannot solve $\mathsf{PPAD}$).

We are not exactly there, in fact. The recent breakthrough result of Peikert and Shiehian (the last paper in the list I gave previously) showed that for important relations, we can build correlation-intractable hash function under well-established lattice problems, such as learning with error, or the SIS problem; however, the sumcheck relation is not captured by this work.

Still, CHKPRR, building on [this work](https://eprint.iacr.org/2018/1004.pdf) showed that one can build a correlation-intractable hash function under the assumption that any of many concrete constructions of fully-homomorphic encryption schemes has quasi-optimal circular security against superpolynomial time attacks.

Let's break down this assumption:

* Fully homomorphic encryption (FHE) is a primitive which we know how to build under a variety of lattice assumptions. If the scheme must only evaluate bounded size circuits, we know in fact how to build it under the standard learning with error assumption.
* Circular security states that the FHE should be hard to break even when it is used to encrypt its own secret key. This is stronger than the usual security notion, which does not allow key dependent messages. It is a major and long standing open problem to build a circularly-secure FHE under a standard lattice assumption, such as LWE. Still, a decade after Gentry's first FHE construction and a lot of cryptanalysis attempts, the circular security of established FHE candidates has itself become a relatively safe-looking assumption (even against quantum computers), and we do not know of any attack that exploits key-dependent encryptions in a nontrivial way.
* quasi-optimal hardness means that all polynomial algorithms have exponentially low probability of breaking the scheme (i.e., probability $2^{\omega(\log \lambda) - \lambda}$, where $\lambda$ is the security parameter). Note that while we might know non-trivial exponential time algorithms, that would break the scheme with non-negligible probability in time $2^{c\lambda}$ for some $c < 1$, we do not know of any *polynomial time* algorithm that breaks the scheme with a probability $2^{-c \lambda}$ for some $c < 1$.
* Finally, we want all the above to still hold if we allow superpolynomial running time to the attacker. This is still in line with what known algorithms can achieve.

All in all, this is clearly not a great, highly plausible and well-established assumption. However, it creates a very interesting connection: it connects the hardness of solving $\mathsf{PPAD}$ with a quantum computer to the question of obtaining strong nontrivial improvements over the best known quantum algorithms to attack important lattice-based cryptographic primitives (fully homomorphic encryption), which is a well-investigated question.

Of course, one of the main open questions left by CHKPRR is to build a correlation-intractable hash function for the sumcheck relation under a better lattice-based assumption - ideally, the LWE assumption. This seems non-trivial, but not implausible, given that this is a very recent line of work, where many surprising results have already been achieved for other interesting relations.

**EDIT**

Apparently, the above result has just been improved in [this paper](https://eprint.iacr.org/2020/860.pdf) to rely solely on the subexponential hardness of LWE (together with the average case hardness of $\#$SAT). This is a major and impressive improvement (not yet peer reviewed, but from very strong researchers, hence very believable) which provides very strong support (essentially as strong as we could hope for using well-studied cryptographic assumptions) for the hypothesis that PPAD is beyond the power of quantum computers.

> **Comments:**
> **username_0**: Dear Geoffroy, very many thanks for your great answer!  
> **username_3**: You are welcome. I just edited by answer to mention a very recent result that shows PPAD hardness under a much, much better assumption, the subexponential hardness of LWE, which is widely believed to hold against quantum computers. This essentially resolves the main open problem from the paper I discussed in my answer, of basing PPAD hardness on some of the most well-studied plausibly quantum-secure cryptographic assumption (the previous paper was more of a win-win result, showing that quantum attacks on PPAD hardness would provide non-trivial speedups for attacking important crypto schemes).  

---

