Polynomial-time Quantum Algorithms for Lattice Problems

Question

A new paper, by Yilei Chen, whose title is Quantum Algorithms for Lattice Problems (https://eprint.iacr.org/2024/555) appeared on eprint and it claims to solve hard lattice problems, such as the approximate (gap) shortest vector problem ($\gamma$-SVP), in quantum polynomial time for approximation factors asymptotically larger than $n^{4.5}$, i.e., for $\gamma \in \Omega(n^{4.5} \cdot polylog(n))$.

That is a huge surprise, since (as far as I know) all the current quantum algorithms for $\gamma$-SVP with polynomial approximation factor run in exponential time. Moreover, $\gamma \approx n^{4.5}$ is a rather small approximation factor (I am sure many fully homomorphic encryption schemes use larger $\gamma$, thus, they would be insecure).

Can anyone assess if this paper is correct or its impact?

We had already some cases where efficient quantum algorithms for lattice problems were discovered, but they turned out not being correct or only worked for simple special cases

Answer 1

Current status regarding the correctness

TL;DR: the attack is not working.

Update: Since April 18 a bug has been found in the paper and the author retracted their claim:

Further details are listed below, including on this attack in mistake 4. Before this:

Mistake 1 (will be easily fixed)

So as @swineone mentionned, this article A Note on Quantum Algorithms for Lattice Problems mentions a mistake in the current version of the preprint:

Our observation is very simple and can be summed up as that the parameter choices are impossible

But the author claim on his website here that this is fixed. I (and integretor) mentionned it below @swineone's answer, but for the posterity, here is a screenshot:

About the question raised in https://eprint.iacr.org/2024/583.pdf​: For our quantum algorithm, it suffices to use κ ∈ O( log n / log(log n) ), as Omri pointed out at the end of the note. I have thought about the prime number density issue, so I wrote κ ≤ O(log n) in the beginning of Section 3.2, but then I forgot to change κ ∈ O(log n) in the statement of Lemma 3.6, which causes a confusion. In fact, we only need D, p_1, p_2, p_3, ... p_kappa to satisfy 2D^2p_1p_2p_3 ... p_kappa = M \in poly(n), so it is even possible to take kappa \in O(1), say kappa=10, but that would require p_2, p_3, ... , p_kappa to be small polynomials in n, which will make the approximation factor for GapSVP slightly worse (but still polynomial in n). I thank Omri Shmueli for pointing this out. The eprint version will be updated later.

The github link points to https://github.com/wildstrawberry/ComplexGaussian

Mistake 2 (seems to be fixed)

In section 3.3: As reported in this twitter thread https://twitter.com/SmartCryptology/status/1780278393465892928 a mistake was made on

I cannot see how the product p2...pk = -1 mod p1 and not 1 mod p1. […]

Yet, a bit later in this thread:

Yilei has confirmed to me one can ignore the p2...pk = -1 mod p1 condition entirely It was put in there to avoid having to carry around an extra constant of c' = p2...pk mod p1. Still got problems with this bit of the method though.

Mistake 3 (not affecting conclusions)

In section 1.1, quoting Hans in a discord channel "Small error when discussing Kyber: k should be chosen from {2, 3, 4}, not {3, 4, 5} (but this does not affect his conclusion)"

Mistake 4 (invalidating the article)

Vidick and Hongxun Wu independently found a mistake in the article that the author is unable to fix, invalidating the result. From http://www.chenyilei.net/:

Update on April 18: Step 9 of the algorithm contains a bug, which I don’t know how to fix. See the updated version of eprint/2024/555 - Section 3.5.9 (Page 37) for details. I sincerely thank Hongxun Wu and (independently) Thomas Vidick for finding the bug today. ​ Now the claim of showing a polynomial time quantum algorithm for solving LWE with polynomial modulus-noise ratios does not hold. I leave the rest of the paper as it is (added a clarification of an operation in Step 8) as a hope that ideas like Complex Gaussian and windowed QFT may find other applications in quantum computation, or tackle LWE in other ways.

The paper has been updated with this note page 37, the error being that the equation $|\psi_{8.g}\rangle$ is wrong:

Thomas Vidick wrote here:

Implications

Edit: these implications do not hold anymore since the paper is retracted. Yet I'll keep them here in case a similar claim is made in the future.

So as the paper mentions:

Let us remark that the modulus-noise ratio achieved by our quantum algorithm is still too large to break the public-key encryption schemes based on (Ring)LWE used in practice. In particular, we have not broken the NIST PQC standardization candidates. […] We leave the task of improving the approximation factor of our quantum algorithm to future work.

However, as far as I understand, it does break a fair amount of papers that rely on a stronger assumption, for instance the security of LWE with superpolynomial noise ratio. This includes notably (sorry, this list is biased towards protocols I'm more familiar with):

• Many FHE schemes like [BGV14] "Fully Homomorphic Encryption without Bootstrapping" https://eprint.iacr.org/2011/277.pdf would be broken. However, it seems like TFHE still resists against this attack.
• This also applies to some quantum FHE schemes, like [Mah18]. While [Bra18] only relies on LWE with polynomial noise ratio, I don't know yet if the attack applies here as we would need to check the exact degree of this polynomial.
• This also break most classical client quantum remote state preparation protocols. For instance, most of my own protocols [CCKW18,CCKW19,CGK23] would be broken, and as far as I understand [GV19] would also be broken (note that their security is implicitly polynomial already). The only candidate I'm aware of that might not be broken is one candidate in [CCKW19] (the one in section 7) where we explicitly try to stay away from LWE with superpolynomial noise ratio, but we rely on a conjecture that we would like to avoid… but I'd need to check exactly the degree of the polynomial we get, even if I'd expect that we can get a degree as low as we want if we accept to pay the price with higher complexity. There is also [AMR22] that builds TCF from isogenies, but it is not clear (at least to me), if this can be used directly to get RSP with a security that scales superpolynomially (at least for the blindness property).

A longer discussion can be found on https://nigelsmart.github.io/LWE.html. You may also be interested by this short Aaranson blog post https://scottaaronson.blog/?p=7946, by discussions on this discord group, and by this forum.

Nevertheless, if this paper turns out to be correct, it would strongly decrease the confidence that people have regarding lattice-based cryptography, that was believed to be the best candidate so far for many applications, as it was not only widely studied but it also has some nice properties that other candidate miss (worst case to average case reduction, usable to build FHE schemes, especially in this superpolynomial noise ratio regime).

Answer 2

Probably it will take some time for the experts in this community to carefully review the paper to see whether it works or not, since it is quite long and technical. Meanwhile, I feel members of this forum can contribute a lot to this long process by posting potential issues/flaws in this paper.

I am neither an expert in quantum computing nor an expert in lattice-based cryptography, so please forgive me for posting a naive question here. In the proof of Lemma 3.9, the author says: We start from preparing a uniform superposition over $\mathbf{v} \in L \cap \mathbb{Z}^n_{Dq}$ and a complex Gaussian state \begin{equation} \sum_{\mathbf{v} \in L \cap \mathbb{Z}^n_{Dq}} |\mathbf{v} \rangle \otimes \sum_{\mathbf{y} \in \mathbb{Z}^n \cap (r\log n) \mathcal{B}^n_{\infty}} \rho_r(\mathbf{y}) \cdot \exp \left(\frac{- \pi i ||\mathbf{y}||^2}{s^2} \right) | \mathbf{y} \rangle. \end{equation} Here comes my question: is the preparation of such a superposition really of polynomial time?

This superposition includes a summation over the vectors $\mathbf{v} \in L \cap \mathbb{Z}^n_{Dq}$, does this mean we have to know which vectors are in the finite set $ L \cap \mathbb{Z}^n_{Dq}$? But $L$ is of the form \begin{equation} L = D \cdot L_q^\perp(\mathbf{A}), \end{equation} for a general matrix $\mathbf{A}$, the task of determining the finite set $ L \cap \mathbb{Z}^n_{Dq}$ is not trivial from what I see, which involves finding all the short vectors of $L$. So if you know about all the vectors in $ L \cap \mathbb{Z}^n_{Dq}$, does this mean you know about the short vectors already?

For example, if you know an almost orthogonal basis of $L$, you might be able to find $ L \cap \mathbb{Z}^n_{Dq}$ quite efficiently, but this already defeat the whole purpose of the quantum algorithms in the paper.

Answer 3

A new paper on ePrint (A Note on Quantum Algorithms for Lattice Problems) claims to have found an error on that paper. Quoting: "Our observation is very simple and can be summed up as that the parameter choices are impossible. (...) We provide a proof to our claim regarding the impossibility for the algorithm’s parameters." However, they note that: "Our claim only invalidates the current version of the paper." -- thus, a fix may be possible.

Answer 4

Yilei Chen published an update on his website yesterday saying that "Step 9 of the algorithm contains a bug", and that he does not yet know if it will be possible to fix it.

TLDR: As of right now, the claim of "a polynomial time quantum algorithm for solving LWE with polynomial modulus-noise ratios does not hold".

The bug was pointed out by to researchers independently. I have added the post below.

The article (https://eprint.iacr.org/2024/555) was updated, with a note describing the error on page 37, explaining that the expression of $|\varphi_{8.f}\rangle$ is wrong.