Why is lattice-based cryptography believed to be hard against quantum computer?

Question

Why is lattice-based cryptography believed to be hard against quantum computer?

Learning With Errors(LWE) problem (reduction to SVP) is just one example.

Can you provide some intuition of the hardness?

Answer 1

Why is lattice-based cryptography believed to be hard against quantum computer?

Because no one has developed a quantum algorithm (yet) that breaks these crypto primitives.

Wish we could do better than that, but that is the best we have at the moment. We believe these primitives to be quantum resistant because no one has given evidence otherwise.

Answer 2

I'm unaware of a great answer to this problem. There are "partial answers", but they are not great. Still, they are what I use to (vaguely) explain things, being someone interested in lattices who does not work on quantum algorithms.

First

Grover's algorithm is quite general and applies to many situations, so I find it hard to believe that quantum computers won't provide some kind of speed-up.

The claim isn't that quantum algorithms don't get speedups (they do), its that only in limited cases do they get what are known as super-polynomial speedups. For a problem $P$, let $T_c$ and $T_q$ be the running times of the best classical and quantum algorithms. The speedup of $P$ is the function $f(x)$ such that $f(T_q) = T_c$.

As an example, Grover search generally gives quadratic ($f(x) = x^2$) speedups when applied to a problem. This means that if you have a classical algorithm of running time $T_c$, you generally get a quantum algorithm of running time $\sqrt{T_c}$. For cryptographic problems, we generally hope that $T_c = 2^{an}$ for some constant factor $a$. We can maintain security (in the presence of a quadratic quantum speedup) by reparameterizing from $n\mapsto 2n$. In fact, I believe this is the motivation for using AES256 rather than AES128, whenever you see people doing this.

So what problems admit super-polynomial quantum speedups? I'm unaware of any nice general theory of this unfortunately. Two notable problems that don't yet are

1. The Graph Isomorphism problem, and

2. LWE.

Of course, there are many problems, and many of them quantum computers probably don't know how to solve. Why mention those two? The answer is that they can be viewed as instances of the Hidden Subgroup Problem. I won't technically define this, but it is a (general) problem parameterized by some group $G$. By appropriately setting this group $G$ to be various quantities, one recovers (essentially)

1. integer factorization,
2. the discrete logarithm problem, and
3. other problems that admit large quantum speedups (but are less well-known cryptographically).

This is to say that there exist groups $G_{factoring}, G_{dlog}, G_{graph-iso}, G_{LWE}$ such that solving the hidden subgroup problem over $G_P$ suffices to solve $P$. Can we at least say that the groups $G_{factoring}, G_{dlog}$ share some similarities that $G_{graph-iso}$ and $G_{LWE}$ don't? The answer is yes.

In particular, a line of research has generalized Shor's algorithm to the abelian hidden subgroup problem, so if/when $G_P$ is an abelian group, $P$ is in $\mathsf{BQP}$. This is not a bi-impliciation --- someone could drop an efficient algorithm for the non-abelian hidden subgroup problem tomorrow. But still, it can be seen as pointing to some mathematical structure that limits (current) techniques at least. For the record, $G_{LWE}$ is a Dihedral group, and $G_{graph-iso}$ is a symmetric group.

While this is motivation you can give (and people do often), I'm not particularly sure its good personally. It sort of points to "LWE is safe, because Graph Isomorphism is another hard problem". But Graph Isomorphism is a famously easy hard problem --- it can be solved in quasipolynomial time classically. Perhaps comparing LWE to a (relatively easy) classical problem isn't the most flattering to LWE. There are also some technical reasons why Dihedral groups are the "least non-abelian non-abelian groups", but I do not believe this is in a way that is known to impact the resulting hidden subgroup problem. Roughly, abelian/not makes a big difference here because Fourier transforms are much nicer of abelian groups (not just in the setting of quantum computation), and the quantum fourier transform is key to the efficient solutions to the abelian HSP. This starts getting pretty mathematical pretty quickly though.

Moreover, there are broader reasons this general story is perhaps not the most convincing. There are various theorems in the literature which says that

(Breaking certain lattice-based cryptography) implies quantum algorithms for (certain worst-case lattice problems).

These worst-case lattice problems are interesting in the sense that they plausibly have non-cryptanalytic uses (factoring is mostly useful for breaking cryptography). For example, an efficient solution to the closest vector problem implies optimal decoding algorithms for (nearly optimal) codes for the Additive White Gaussian Noise channel, which coding theorists would be happy about.

For better or worse, people rarely parameterize their cryptosystems so that the aforementioned theorems hold though. For example, all reductions I know of say that the noise-to-modulus ratio must be large $\Omega(\sqrt{n})$, but people typically set it to some constant $O(1)$ (such as 8 or something). This isn't known to make classical attacks much better, but it means the aforementioned theorems don't hold --- quantum computers that break it need not making coding theorists happy anymore.

Moreover, there are certain (fairly weird) instantiations of LWE that do admit non-trivial quantum algorithms. There additionally exist lattice-based cryptosystems (that used non-standard underlying problems) that have fallen to quantum attacks (summary here).

It'd be great for someone who works on quantum algorithms to give an answer to this question, but for someone who doesn't but works on lattice crypto I would summarize things as

1. LWE is (plausibly) hard as nobody has given algorithms for it for a while, despite natural motivation from the coding-theory community (and cryptanalysts of course)

2. there is a natural barrier to extending current techniques to LWE as it corresponds to a non-abelian instance of the hidden subgroup problem, while exponential speedups are (mostly) limited to abelian instances of HSP.

3. the list of computational problems for which we get non-trivial quantum speedups is really much shorter than most people assume (especially after reading about Grovers, which is a broad technique, but not a concern cryptographically except for setting parameters).

That being said, if someone dropped a BQP algorithm for LWE instances that aren't covered by worst-case to average-case reductions, but are used in cryptography (low noise rate), it would both

1. break a ton of existing lattice-based crypto schemes, and

2. not necessarily shake confidence in the quantum hardness of (properly parameterized) LWE (as it wouldn't contradict the underlying worst-case lattice problems being hard for quantum computers).

Who knows how likely this is. It would make various mailing lists much more exciting for a number of years though :)

Answer 3

Let's ask why do we think Integer factorization or discrete logarithm are hard for classical computers?

We don't have a better lower bound than a lot of smart people have tried find an efficient algorithm for a long time and have thus failed.

It's worth noting we don't think these problems are NPC, in fact most believe they are not. If discrete logarithm is NPC the polynomial heirarchy collapses which is considered unlikely to be the case.

With symmetrical ciphers like AES we have even less elegant math supporting. But the security proof is the same. Many smart people have looked for an efficient solution and failed to find one.

When looking at lattice based problems and quantom computers it is much the same. They are definetly preferred over problems we know for a fact fail in the face of a quantom computer, and many smart people looked for an efficient quantom algorithm and failed.

So we build cryptographic solutions by building on well studied problems.

Answer 4

I would like to add one answer, which is not specific to lattice-based cryptography.

Among the usual candidates of post-quantum crypto, we have lattice-based crypto, multivariate-polynomial based crypto, and code-based crypto. What is common among these is that, there are NP-hard problems behind each of these.

So far, quantum computers are not known to solve all of NP problems efficiently. (Like, in the sense of $\mathrm{NP}\subseteq\mathrm{BQP}$.) It is quite a stretch of existing evidences, but, then, if a problem is closely related to such an NP-hard problem, perhaps we might say that it is not quite unreasonable that a quantum computer may also find it hard to solve such a problem.

Of course, an NP-hard problem is almost never used in crypto as it is. In case of the lattice-based crypto, the approximation factors of these lattice problems used in crypto is much bigger than the regime where the problems become NP-hard. For multivariate-polynomial based crypto and code-based crypto, to make one-way functions, the problem is modified, additional structures are hidden, and the resulting problem is no longer NP-hard. It is quite true that there are possibilities that these modifications could introduce hidden weaknesses which could be exploited by a quantum computer. But, then again, these might not, and so far that was the case.

(In addition we have hash-based signatures, and also isogeny-based crypto. These are different stories.)

Answer 5

Because lattice based cryptography, for example, the NTRU crypto system, uses polynomial factoring (which despite the name is COMPLETELY different from integer factoring), and quantum computers do not have an efficient algorithm for polynomial factoring at the moment.

Edit: Actually its just certain polynomials: " relies on the presumed difficulty of factoring certain polynomials in a truncated polynomial ring into a quotient of two polynomials having very small coefficients." - https://en.wikipedia.org/wiki/NTRUEncrypt