<p>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.</p>

<p>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 <em>worst-case</em> (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.</p>

<p>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 href="http://web.eecs.umich.edu/~cpeikert/pubs/svpcrypto.pdf" rel="nofollow">A paper</a> by Peikert in 2009 and a <a href="http://arxiv.org/pdf/1306.0281.pdf" rel="nofollow">follow-up paper</a> by Brakerski et al. in 2013 made progress towards this goal by showing classical hardness of LWE under some weaker parameter settings.</p>

CC BY-SA 3.0
2015-11-04T05:04:27.540Z
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!
Daniel Apon
CC BY-SA 3.0
2015-11-04T05:07:47.863Z
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. =)
Daniel Apon
CC BY-SA 3.0
2015-11-05T04:14:09.867Z
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.
Huck Bennett
CC BY-SA 3.0
2015-11-05T15:41:39.380Z
Huck, it turns out your answer is effectively "the" answer, no matter where you look. I asked some serious quantum computing people about it, and the answer was roughly: "Nothing dramatic would change about our understanding of quantum, if there were a fast quantum lattice approximation algorithm. We just don't happen to have one right now."
Daniel Apon
CC BY-SA 3.0
2015-11-05T15:43:50.560Z
(And then there's another can of worms that opens: A fast quantum lattice approximation algorithm, in fact, wouldn't necessarily imply a fast quantum LWE algorithm. But it would certainly destroy our current evidence for believing LWE is quantum resistant regardless...)
Daniel Apon
CC BY-SA 3.0
2015-11-13T00:32:05.773Z
@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.
Chris Peikert
CC BY-SA 3.0
2015-11-13T00:34:35.217Z
@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.
Chris Peikert
CC BY-SA 3.0
2015-11-13T21:55:01.103Z
@Chris: Thanks for the comment. Citation added.
Huck Bennett
CC BY-SA 3.0
2015-11-03T23:25:54.393Z
2015-11-13T21:53:20.107Z
2015-11-13T21:53:20.107Z
Huck Bennett
<p>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 <strong>quantum</strong> attackers.</p>

<p>For instance, the standard paper on $\mathsf{LWE}$, <a href="http://www.cims.nyu.edu/~regev/papers/qcrypto.pdf" rel="noreferrer">Regev2005</a>, 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 <strong>why</strong> a critic might be convinced that such quantum hardness holds.</p>

<p>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 <em>tens of millions</em> (or more) dollars are handed out in cryptography grant money based (<strong>in part</strong>) on this high-level claim.</p>

<p>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!</p>

<hr>

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

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

<ul>
<li>What structural property of factoring allows Shor's algorithm to run
quickly, but appears to be missing from worst-case lattice (approximation) problems?</li>
<li><strong>In particular:</strong> How is this gap related to our current understanding of the Abelian Hidden Subgroup Problem (<strong>HSP</strong>) vs non-Abelian variants of the <strong>HSP</strong>?</li>
</ul>

CC BY-SA 3.0
2015-11-04T01:19:06.590Z
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
CC BY-SA 3.0
2015-11-04T01:21:38.563Z
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
CC BY-SA 3.0
2015-11-04T02:22:13.217Z
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
CC BY-SA 3.0
2015-11-04T10:56:00.173Z
@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
CC BY-SA 3.0
2015-11-13T00:39:28.350Z
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
<reference-request><quantum-computing><cr.crypto-security>
Quantum Hardness of Approximating Lattice Problems
Daniel Apon
# Quantum Hardness of Approximating Lattice Problems

(Asked by: username_0 on 2015-11-03)

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](http://www.cims.nyu.edu/~regev/papers/qcrypto.pdf), 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**?

**Tags:** reference-request, quantum-computing, cr.crypto-security

> **Comments:**
> **username_1**: 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.  
> **username_1**: 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.  
> **username_0**: 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.)  
> **username_2**: @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?  
> **username_3**: 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.  

---

## 1 answers

### Answer by username_4 on 2015-11-03. Score: 9 | Accepted answer

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](http://web.eecs.umich.edu/~cpeikert/pubs/svpcrypto.pdf) by Peikert in 2009 and a [follow-up paper](http://arxiv.org/pdf/1306.0281.pdf) by Brakerski et al. in 2013 made progress towards this goal by showing classical hardness of LWE under some weaker parameter settings.

> **Comments:**
> **username_0**: 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!  
> **username_0**: 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. =)  
> **username_4**: 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.  
> **username_0**: Huck, it turns out your answer is effectively "the" answer, no matter where you look. I asked some serious quantum computing people about it, and the answer was roughly: "Nothing dramatic would change about our understanding of quantum, if there were a fast quantum lattice approximation algorithm. We just don't happen to have one right now."  
> **username_0**: (And then there's another can of worms that opens: A fast quantum lattice approximation algorithm, in fact, wouldn't necessarily imply a fast quantum LWE algorithm. But it would certainly destroy our current evidence for believing LWE is quantum resistant regardless...)  
> **username_3**: @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.  
> **username_3**: @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.  
> **username_4**: @Chris: Thanks for the comment. Citation added.  

---

