# Why do Problems for Post-Quantum algorithms have to be NP-Hard?

The mathematical problems used for Post-Quantum Cryptography problems I came across, are NP-complete, e.g.

• Solving quadratic equations over finite fields
• short lattice vectors and close lattice vectors
• bounded distance decoding over finite fields

At least the general version of these is NP-complete

I am asking myself why these mathematical problems need to be NP-complete (in the general version) and how this is even useful, when instances are used that are not NP-complete

I am unaware of cryptography that is hard solely assuming that $$P\neq NP$$, so I believe you are misunderstanding something. I know the story best when it comes to lattices, so I'll discuss why lattices are solely "adjacent" to an $$NP$$-hard problem.

The story is rather simple, but also technical. Let $$\mathsf{LWE}[n, \sigma, q]$$ be the average-case LWE problem in dimension $$n$$, standard deviation $$\sigma$$, and moduli $$q$$. Regev's quantum worst-case to average-case reduction for LWE states that:

$$\mathsf{SIVP}_{\tilde{O}(nq/\sigma)} \leq \mathsf{LWE}[n, \sigma, q]$$

Where $$\mathsf{SIVP}_\gamma$$ is the short independent vectors problem (think of it like a generalization of the shortest vector problem to finding $$n > 1$$ short linearly independent vectors, where $$n$$ is the dimension of the lattice). Note that the $$\gamma$$ here is an approximation factor that is allowed in the problem.

What is the precise complexity of $$\mathsf{SIVP}_\gamma$$? This highly depends on the parameter $$\gamma$$, but the following should suffice for this post. It is known that $$\mathsf{SIVP}_{\tilde{\Omega}(\sqrt{n})}$$ is in $$\mathsf{AM}\cap co\mathsf{AM}$$. This implies that it is not $$\mathsf{NP}$$-hard unless the polynomial hierarchy collapses to some finite (it looks like 2nd?) level, which complexity theorists view as being unlikely.

This essentially means that while $$\mathsf{SIVP}_\gamma$$ is known to be NP-hard for some $$\gamma$$, the $$\gamma$$ used in lattice cryptography is such that we view it as extremely unlikely that $$\mathsf{SIVP}_\gamma$$ will be NP-hard. Still, for basic protocols one can generally take $$\gamma$$ to be some small polynomial, so $$\mathsf{SIVP}_\gamma$$ is "close" to an NP-hard problem, especially as the smallest approximation factor that we have polynomial-time algorithms for is something sub-exponential iirc.

More generally, NP hardness is the wrong thing to look at in cryptography. What people actually want is some notion of average-case hardness. In lattice cryptography one can formally connect that with worst-case hardness, but not every area in cryptography has such reductions. In areas that don't, the particular worst-case hardness of the problem is not very important --- a problem can have some instances that are very hard while still being bad for cryptography, as it may be hard to generate a hard instance. What is more important is specifying some plausible average-case hard distribution and examining the particular hardness of this.

• A minor quibble on an otherwise great answer: in the SIVP approx factor, the $O$ should be $\tilde{O}$ (or add a tiny $\epsilon$ to the exponent), and it should be mentioned that this reduction is quantum. Apr 17, 2021 at 19:29
1. They don't need to be: isogeny-based cryptography has no connection to any NP-complete problems, as far as I am aware.

2. Generally you want the underlying mathematical problem to be hard, and you can't get "harder" than NP, since (to be very imprecise) the secret key of a public-key cryptosystem acts like a "witness" for any hard problem you would want to solve. My guess for "why" would be that an NP-complete problem is a good place to start looking for hard problems, so historically that's where they came from.

3. For whether it's useful, I'm not sure there is a definitive answer. Certainly it makes me more confident in the schemes. As an example of why, all the best (generic) attacks against lattice crypto are based on just solving SVP. Unless P=NP I can be reasonably confident that these attacks can't get that much better, and it restricts the avenues of possible alternative attacks to, e.g., an LWE-specific attack that doesn't extend to solve SVP generally. Such an algorithm just feels weird, so that makes me more inclined to believe the scheme is generally secure.

4. This isn't exactly what you asked, but you might also wonder: why not use a scheme based on an NP-complete problem, rather than instances that are not NP-complete? The reason is that NP-complete problems are worst-case hard, not average-case hard. When you use a scheme, you want to be sure that your key, as an instance of some computational problem, is hard; it's no good if you have a guarantee that someone else's key is hard to break. Hence, we need to restrict to subclasses of NP-complete problems. (Lattices go from SVP to LWE; codes go from general decoding to decoding a specific family like Goppa codes; multivariate gets restricted to polynomials formed by some particular process like oil-and-vinegar). The way I think of it is that NP-complete problems must be versatile enough that any other problem can reduce to them, and that versatility creates a lot of easy instances of the problem. I've heard second-hand that there may be deep complexity theory reasons we shouldn't expect an average-case hard NP-complete problem to exist, but that's way beyond my understanding and.

### Problems for post-quantum algorithms do not need to be NP-hard.

The goal of post-quantum cryptography is for the cryptographic scheme to be secure against quantum computers.

For example, a cryptographic scheme in which the hardest part of the decryption algorithm is the factoring of integers is not post-quantum secure because Shor's algorithm for factoring numbers allows you to do the decryption with a cost that is a polynomial of the key size no matter how large the key size gets.

Likewise, many schemes based on elliptic curves can be decrypted by Shor's algorithm for finding discrete logarithms with again a polynomial cost.

However, there's many problems that are not known to be NP-hard for which there is still no efficient quantum algorithm!

As long as decrypting the cryptographic scheme requires some computation for which there is not yet any quantum algorithm that can do the computation efficiently, it can be considered a "post-quantum" scheme, regardless of whether or not there's an NP-hard problem involved. One example would be Supersingular isogeny key exchange which was invented in 2011 by the professor who taught my cryptography class (David Jao) and two of his colleagues.