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?
• From Regev's paper: "The only evidence supporting this conjecture [quantum hardness of GapSVP] is that there are no known quantum algorithms for lattice problems that outperform classical algorithms, even though this is probably one of the most important open questions in the field of quantum computing." Note that he needs quantum hardness because his reduction from LWE is quantum. – Sasho Nikolov Nov 4 '15 at 1:19
• I don't think it's completely fair to say that lattice crypto research is being funded soleley on the basis of its security against quantum attacks. AFAIK (and I am decidedly not an expert) lattice based systems are the only known constructions of fully homomorphic encryption schemes, among other magical things. – Sasho Nikolov Nov 4 '15 at 1:21
• Thanks Sasho, I've updated my remark about "funding of lattice-based crypto" to reflect that LWE/SIS's conjecture quantum-hardness is part of the motivation for funding. (There are of course many other, unrelated reasons involved in real-world funding of anything.) – Daniel Apon Nov 4 '15 at 2:22
• @DanielApon: As is common with such questions, there is a spectrum of rigorousness with which one can answer your clarified question. The obvious (likely for you at least) answer is that cyclical periodic structures abound in multiplicative number theory, making an eigenvalue estimation solution for the DISCRETE LOG (and FACTORING) a promising and ultimately fruitful approach. Furthermore, the hard part of those problems are in effect purely algebraic, which is to say that 'magnitude' plays little role. What comparable structured group action would one suspect, for GapSVP problems? – Niel de Beaudrap Nov 4 '15 at 10:56
• To be clear, Regev's paper is not normally used as a evidence supporting the belief that lattice problems are quantum-hard. Rather, it provides a very useful implication of that assumption. – Chris Peikert Nov 13 '15 at 0:39

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.