PPAD and Quantum

I will attempt to elaborate a bit on why CHKPRR 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. 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,2,3,4,5,6) 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 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^{clambda}$ 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 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.

Two answers that I learnt while writing a blog post 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 by Alan Deckelbaum.

And one historical note: PLS was actually introduced by Johnson-Papadimitriou-Yannakakis in 1988.