7
$\begingroup$

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?
Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ 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. $\endgroup$
    – Sasho Nikolov
    Nov 4, 2015 at 1:19
  • 2
    $\begingroup$ 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. $\endgroup$
    – Sasho Nikolov
    Nov 4, 2015 at 1:21
  • $\begingroup$ 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.) $\endgroup$
    – Daniel Apon
    Nov 4, 2015 at 2:22
  • 1
    $\begingroup$ @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? $\endgroup$
    – Niel de Beaudrap
    Nov 4, 2015 at 10:56
  • 2
    $\begingroup$ 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. $\endgroup$
    – Chris Peikert
    Nov 13, 2015 at 0:39

1 Answer 1

Reset to default
7
$\begingroup$

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.

Improve this answer
$\endgroup$
8
  • $\begingroup$ Hi Huck, thanks for your response (I upvoted :)). To clarify: I'm looking for specific properties of lattice problems and quantum algorithms that differ from the generic answer one might give for, say, RSA. I'm especially interested in a discussion of Abelian HSP vs non-Abelian HSP. (I've updated my question to reflect more clearly what I'm looking for in an answer.) Thanks again! $\endgroup$
    – Daniel Apon
    Nov 4, 2015 at 5:04
  • $\begingroup$ P.S. If there truly is nothing concrete further to say (i.e. no one gives an answer especially illuminating this Abelian vs non-Abelian HSP issue w.r.t. quantum algorithms), I will accept your answer after some time. =) $\endgroup$
    – Daniel Apon
    Nov 4, 2015 at 5:07
  • 1
    $\begingroup$ Hi Daniel - I looked at your other questions and research it looks like you are very familiar with LWE already, so I guess nothing I said here is new. I still think the generic answer stands, but I'd be very curious to hear about any connections that you find. $\endgroup$
    – Huck Bennett
    Nov 5, 2015 at 4:14
  • 1
    $\begingroup$ @Daniel, fast quantum lattice approx algorithms would defeat LWE, because LWE is an average-case version of the standard lattice problem BDD (bounded-distance decoding), which is solvable using, say, an approx-SVP oracle. $\endgroup$
    – Chris Peikert
    Nov 13, 2015 at 0:32
  • 1
    $\begingroup$ @Huck regarding the last paragraph of your answer, my STOC'09 paper would be the more appropriate citation -- it gives the first worst-case hardness for LWE via classical reduction. The paper with Brakerski et al piggybacks on that, giving other LWE-to-LWE reductions for more "standard" parameterizations. $\endgroup$
    – Chris Peikert
    Nov 13, 2015 at 0:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.