In An Efficient Quantum Algorithm for Lattice Problems Achieving Subexponential Approximation Factor, the author claims they give a polynomial-time quantum algorithm for solving the Bounded Distance Decoding problem with a subexponential approximation factor on a class of integer lattices. What does this result mean? Will it imply the insecurity of lattice cryptography? Is it as important as quantum algorithm for factoring by Peter Shor?

  • 3
    $\begingroup$ Before this work implies the insecurity of lattice cryptography, we'll need Cryptographically Relevant Quantum Computers. [Late addition: this comments the obvious: the question's "Will ((this result) imply the insecurity of lattice cryptography?" could only be with CRQC] $\endgroup$
    – fgrieu
    Sep 22 at 6:29
  • 10
    $\begingroup$ @fgrieu One of the major selling points of lattice cryptography is quantum resistance. So the question is whether this new result invalidates that claim. Clearly there is no threat until a quantum computer at stage is built, if such a machine is ever built. However, the question remains as to whether lattice-based cryptography should continue to be a candidate for a post-quantum world. $\endgroup$ Sep 22 at 7:06
  • $\begingroup$ @YehudaLindell isn't it a threat if such a machine is possible? Since the eavesdropper can store the communication and break all. This is why we are using AES-256 not AES-128. $\endgroup$
    – kelalaka
    Sep 22 at 21:13
  • $\begingroup$ @kelalaka it really depends on the application. Some (like authentication) are mildly impacted in the near-term, with minor exceptions (perhaps OS updates or other highly security critical things). $\endgroup$
    – Mark
    Sep 22 at 23:19
  • 8
    $\begingroup$ There is now a note by Léo Ducas & Wessel van Woerden claiming that classical LLL suffices to get pretty much the same result. $\endgroup$
    – yyyyyyy
    Sep 23 at 7:04

There is no public paper available yet, so this answer is preliminary and based on what was presented in the talk and the follow-up discussion. A full understanding cannot be reached until there is a paper to verify, evaluate, and compare to prior work and known results. However, a good understanding of the situation already seems to be emerging.

The tl;dr is: the special problem the authors address is classically easy to solve using standard lattice algorithms (no quantum needed), as shown in this note. Moreover, the core new quantum step can instead be implemented classically (and much more simply and effectively) as well. So, the work doesn’t show any quantum advantage versus what we already knew how to do classically, nor anything new about what we can do classically. Details follow.

The clause “on a class of integer lattices” is a very important qualifier. The BDD problem the authors address is one where the lattice is “$q$-ary” and generated by a single $n$-dimensional mod-$q$ vector (or a small number of them), the modulus $q \gg 2^{\sqrt{n}}$, and the target vector is within a $\ll 2^{-\sqrt{n}}$ factor of the minimum distance of the lattice. This setting is far from anything that has ever been used in lattice cryptography (to my knowledge), so the result would not have any direct effect on proposed lattice systems. Of course the broader question is whether the techniques could lead to stronger results that do affect lattice crypto.

Based on the description given in the talk, several expert attendees believe it’s very likely that the special lattice problem the authors address is already easily solvable using known classical techniques (no quantum needed). UPDATE: this has turned out to be the case, and is substantiated in this note. In other words, the particular form of the BDD problem makes it easy to solve in known and unsurprising ways. The algorithm is merely the standard sequence of LLL basis reduction followed by Babai nearest-plane decoding, but showing that this actually works relies on some deeper (but previously known) properties of LLL than the ones that are usually invoked.

What about the broader question: could the main techniques lead to stronger results that we can’t currently obtain classically? It turns out that what the core quantum step accomplishes, the “worst-case to average-case” transformation, can be done classically (and more simply and efficiently) using a well known randomization technique—what’s called the “LWE self reduction“ or “($q$-ary) BDD to LWE reduction.” See Section 5 and Theorem 5.3 of this paper and the earlier works cited therein for details.

More precisely, $n$-dimensional $q$-ary BDD for relative distance $\alpha$ (the problem considered by the authors) classically reduces to LWE with error rate $\alpha \cdot O(\sqrt{n})$. While this reduction looks unnecessary to solve the original BDD problem in question, it shows that the core new quantum step can be replaced by something classical that performs at least as well (and likely even better in terms of parameters). This indicates that the main quantum technique probably does not hold any novel or surprising power in this context.

  • $\begingroup$ The use of approximate eigenvectors, whose eigenvalue has the "secret", was new to me. Is that a well-known technique in quantum lattice cryptanalysis, or is it possible it can find a more powerful application than a $n\rightarrow\sqrt{n}$ reduction? $\endgroup$
    – Sam Jaques
    Sep 24 at 20:38
  • $\begingroup$ I didn’t really follow what they were getting at with that. But “approximate eigenvectors” (in a different, non-quantum sense) are a common tool in the latest generation of LWE-based FHE schemes, a la GSW. $\endgroup$ Sep 24 at 21:05

One could give a much longer answer to this question (and I would be quite interested in seeing someone like Chris's perspective), but the following two points probably suffice for a non-specialist.

Approximation Factors: The main way this attack should be seen as (potentially) threatening to lattice-based cryptography is via the possibility of future improvements. The approximation factor this targets (which I believe is $2^{n^{1/2}}$) is large enough that even if LWE was classically weak in this range, one could still construct things like:

  • PKE
  • Digital Signatures
  • FHE

E.g. most of what you might care about would still exist. So the current attack itself does not really impact the main body of "practical" lattice-based cryptography, although future improvements to the attack are of course possible.

The Possibility of Dequantization: The attack has two parts:

  1. A (quantum) dimensionality reduction step (from $n\to \sqrt{n}$)
  2. Use standard classical techniques to solve the $\sqrt{n}$-dimension instance.

A number of people suggested the possibility of dequantizing the first step, via things like taking random linear combinations (say with Gaussian coefficients) of the basis vectors. If this dimension reduction works, one gets BDD with approximation factor $2^{n^{1/2}}$ in polynomial time (I believe).

While this would make the algorithm itself stronger, it would also make it less concerning in a certain sense. This is because we (classically) have a fairly decent idea of how hard lattice problems are. By this, I am in particular thinking of things like:

  1. The various "fine-grained" hardness results that exist (say under the Exponential Time Hypothesis, or variants of it),
  2. the recent lattice sieving lower bounds, and
  3. hardness results in the presence of pre-processing (for example CVPP hardness results).

Of course these do not rule out all possible attacks, but they should be mentioned as a growing body of formal evidence for the classical hardness of lattice problems. This is to say that the main concerning thing about the linked talk is the existence of a non-trivial quantum speedup --- if this is dequantized, we are back in the setting of classical computing, where our understanding of the hardness of lattice problems is better.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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