New quantum attack on lattices (or Shor strikes again)?

Question

Lior Eldar and Peter W. Shor published a paper on arXiv.org in which they present a new quantum algorithm against a variant of BDD. They claim that their new algorithm can efficiently solve the following problem:

Given a lattice $L$, a vector $v$, and numbers $b = {\lambda}_1(L)/n^{17}$, $a = {\lambda}_1(L)/n^{13}$ decide if $v$'s distance from $L$ is in the range $[a/2, a]$ or at most $b$, where ${\lambda}_1(L)$ is the length of $L$'s shortest non-zero vector

Moreover they state that

improving these parameters to $a = b = {\lambda}_1(L)/\sqrt{n}$ would invalidate one of the security assumptions of the Learning-with-Errors (LWE) cryptosystem against quantum attacks.

Now, while I assume the authors refer here to Regev's original proposal, nowadays, there exists a zoo of LWE-type assumptions, used in lattice-based crypto. These assumptions mainly differ in the choice of parameters / used distributions.

My question is, does anyone have an idea how many of these or which class of LWE-type assumptions are broken by the proposed algorithm?

Answer 1

As mentioned in the comments, there is a serious flaw in the paper, and it has been withdrawn: see https://groups.google.com/forum/#!msg/cryptanalytic-algorithms/WNMuTfJuSRc/OtQMLRXgBwAJ and part (3) of http://www.scottaaronson.com/blog/?p=2996

Answer 2

The authors themselves point out that this doesn't break lattice-based assumptions used in crypto. To quote:

Lattice problems have received enormous attention in recent years, mainly because of their algebraic structure has allowed constructions of cryptographic primitives, culminating in the Learning-with-Errors (LWE) encryption scheme due to Regev [Reg09]. Our algorithm does not invalidate the security assumption of LWE against quantum attacks, yet. To do that, one would have to improve the performance of the algorithm to solve $gapBDD_{\gamma_1,\gamma_2}$ for $\gamma_1 = \gamma_2 = \sqrt{n}$, which would make it equivalent to say, solving $gapSVP_{\tilde O(\sqrt{n})}$. We point out, that even achieving such an algorithm would not ”break” LWE per-se. To do that - one would have to actually find a quantum algorithm that solves the full version of gapCVP to some polynomial factor. Such a task, we believe, would require adding new techniques to the ones suggested here: see next item.

Furthermore:

Our proposed algorithm falls short of solving the full version of gapped-CVP and requires an additional promise that the input vector is at least ”somewhat close” to the lattice. We believe that this is not an artifact of the proof, but goes to the core of the scheme: we require crucially, that if we consider adjacent lattice points, and test their inner-product w.r.t. some vector $v$, then these vectors would have similar inner-product with that vector. That can only happen if $v$ is ”close” to a dual lattice, the extreme point of which is that $v \in NL^*$ in which case both of these inner products are by definition 0. Removing the assumption on $v$ would hence entail a completely different scheme, we believe. As an additional example of this difference, we note that an instance of gapCVP, like that of gapBDD also includes two numbers $a, b$, where $b/a = poly(n)$, and we are asked to distinguish whether or not a vector is within distance at most $a$ or at least $b$ from $L$. Yet for gapBDD the knowledge that both of these numbers are some relative fraction of $\lambda_1$ yields some implicit information about the length of the shortest vector of the input lattice.

So, current schemes for encryption etc. are not affected per se. Furthermore, the authors believe that this is a fundamentally different problem. However, it is quite likely that this result will cause a flurry of research to see if it can be extended.

=================================================

An update on this; it appears that all may be fine with LWE!

Answer 3

Unless I misunderstood the definitions, an algorithm for the problem in Definition 1 (i.e. their main result) is in fact enough to attack decision-LWE if the noise is small. The fact that they need a promise that the point is always close to the lattice doesn't seem to be a problem.

A decision-LWE problem mod q, where samples are of dimension n and the noise is a gaussian in each coordinate with standard deviation s, can be converted into the following decision problem: given a random lattice $L$ (where "random" is a prticular distribution induced by decision-LWE) of dimension $2n$, one is given a target that is either less than a distance $s\cdot\sqrt{2n}$ away (actually, there should be a small constant close to $1$ being multiplied by the preceding upper bound, but let's ignore it for simplicity) from $L$, or it is in a uniformly random coset of $\mathbb{Z}^{2n}/L$. In the latter case, the distance to $L$ is proportional to the covering radius - so it is quite far away. (I should mention, there are ways to map decision-LWE to lattices of different dimension, but for simplicity, let's just stick with the above mapping.)

So here is how one would go about solving this problem using an oracle for the problem in Definition 1. Set $b=s\cdot\sqrt{2n}$ and $a=b\cdot n^4$ (they need this relationship between $a$ and $b$). The first thing we need to do is figure out what is the output of the oracle if we feed it random lattices (the same kind that we generate in decision-LWE instances) and random targets. Note that the promise of the target being near the lattice is not satisfied, but the algorithm must still output something. We can learn what the output (or the distribution of the output) is by feeding it randomly generated lattices with random targets. If it outputs something different than when the target is $<b$ away form the lattice, then we can use it to solve the problem defined in the previous paragraph. On the other hand, if its output is the same as when the target is $<b$ away, then it must be different from its output when the target is in the interval $[a/2,a]$. Thus we can use this oracle to solve the Decision-LWE problem when the standard deviation of the noise is s such that $s\cdot\sqrt{2n} \in [a/2,a]$. This is an even harder problem since the noise is larger. So at worst, we can solve Decision LWE when the noise has standard deviation $s=b/\sqrt{2n}$.

Now the question is, what is $b$? They define $b=\lambda_1(L)/n^{17}$. So we need to know $\lambda_1(L)$ for the $L$ that is induced by the decision-LWE problem. It turns out that the shortest vector length is close to the Minkowski bound. The determinant of $L$ is $q^n$, and its dimension is $2n$. So $\lambda_1\approx\sqrt{n}\cdot \sqrt{q}$. So that's it -- whenever $s/\sqrt{n}<\sqrt{n}\cdot \sqrt{q}/n^{17}$ (or $s<\sqrt{q}/n^{16}$), an algorithm that solves the problem in Definition 1 can be used to solve decision-LWE where $s< \sqrt{q}/n^{16}$.

These parameters are quite outside the scope of anything that is currently being proposed (anything with those parameters that is not already broken by LLL is going to be horribly inefficient), but of course they could improve. Furthermore, their description is of an algorithm that works in the worst-case -- heuristically, it might perform better. If this $n^{17}$ gets to $n^5$, some reasonable things may start getting broken. An if it goes down to linear, then encryption/signatures may become affected.

I think the first thing to do, though, is to wait until some experts in quantum algorithms verify this paper. If they agree that it's correct, then things will become interesting.