Quantum Hardness of Approximating Lattice Problems A common claim in lattice-based cryptography is that cryptosystems based on the Learning with Errors ($\mathsf{LWE}$) problem are hard to break (for a per-system definition of "break") for quantum attackers.

For instance, the standard paper on $\mathsf{LWE}$, Regev2005, makes multiple references to the security of $\mathsf{LWE}$-type systems based on the quantum hardness of solving, say, $\mathsf{GapSVP}_\alpha$ for polynomial approximation ratios $\alpha$. But, as far as I see, there is no mention here as to why a critic might be convinced that such quantum hardness holds.

Across the host of lattice-based cryptography, the reference is generally made back to Regev's first paper, with no more explanation. And this association is quite important to the broader theory community, because likely tens of millions (or more) dollars are handed out in cryptography grant money based (in part) on this high-level claim.

Searching the CSTheory site also turns up no answer to this question. Perhaps there is a simple place to look up this information online.. in which case, consider this question the "CSTheory catalogue" of where to find this information!



$\underline{\rm Question}:$ What is the proper, "standard" justification for why it is believed hard for efficient, quantum algorithms to approximate $\mathsf{GapSVP}_\alpha$ to within polynomial approximation factors $\alpha$?

$\underline{\rm Question\; Clarification\, /\, What\; I'm\; Looking\; For:}$


What structural property of factoring allows Shor's algorithm to run
quickly, but appears to be missing from worst-case lattice (approximation) problems?
In particular: How is this gap related to our current understanding of the Abelian Hidden Subgroup Problem (HSP) vs non-Abelian variants of the HSP?
The answer to your question is the same as with many other such assumptions in cryptography: despite a lot of effort no one has found any substantially faster quantum algorithms for lattice problems. Why do we assume that RSA is secure? We don't have any particular justification for its classical hardness other than the fact that no one has found any fast algorithms for it, and we know that it is vulnerable to quantum attacks. Despite this we trust it to protect billions of dollars of e-commerce.

On the other hand, the situation is not really the same. There is much better justification for LWE-based systems being secure. What makes LWE appealing is that it's based on the worst-case (quantum) hardness of lattice problems. As you probably know, a holy grail of crypto is to derive average-case-hard primitives like one-way functions from worst-case hardness assumptions like $P \neq NP$. Regev's reduction is a big step in this research program, and as far as I know there are no non-lattice based schemes whose security is based on worst-case hardness assumptions.

Finally, it's worth noting that LWE may still be secure against classical attacks even if there are efficient quantum algorithms for lattice problems. A major open problem in lattice-based cryptography is to prove classical hardness of LWE with parameters that match the quantum reduction. A paper by Peikert in 2009 and a follow-up paper by Brakerski et al. in 2013 made progress towards this goal by showing classical hardness of LWE under some weaker parameter settings.