62
$\begingroup$

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

$\endgroup$
8
  • 5
    $\begingroup$ For those who were wondering: "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.... We leave the task of improving the approximation factor of our quantum algorithm to future work." Note that CRYSTALS--Kyber falls within these schemes. So on the one hand it seems that it isn't broken yet, but the paper seems to leave it as an implication that it could be broken. $\endgroup$
    – Maarten Bodewes
    Apr 11 at 7:55
  • 1
    $\begingroup$ @MaartenBodewes Theoretical possibility is one thing. Whether it's practically possible to build a QC running the currently proposed algorithm, and whether it's more-equally-less efficient when compared to Shor's is whole another thing. Not to mention the further obstacles of future optimizations enabling it to actually break Kyber (or even Dilithium). $\endgroup$
    – DannyNiu
    Apr 11 at 8:58
  • 3
    $\begingroup$ @MaartenBodewes I saw this remark. But still, the approximation factor $\gamma \approx n^{4.5}$ is very small. Well-established schemes, such as BGV and CKKS, base their security in lattice problems with approximations factors larger than any $poly(n)$ when implemented with bootstrapping. $\endgroup$ Apr 11 at 12:30
  • 3
    $\begingroup$ This is not about whether this threatens Lattice Cryptography today. This is about whether it has potential to threaten the quantum-safety of Lattice Cryptography in the future. And I would say this increases the chances significantly... (if paper isn't flawed) $\endgroup$
    – mti
    Apr 11 at 14:24
  • 2
    $\begingroup$ Nigel Smart wrote a webpage about the paper and its implications $\endgroup$
    – Ruggero
    Apr 16 at 13:29

4 Answers 4

26
$\begingroup$

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:

enter image description here

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:

enter image description here

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:

enter image description here

Thomas Vidick wrote here:

enter image description 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).

$\endgroup$
11
$\begingroup$

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.

$\endgroup$
6
  • 3
    $\begingroup$ "... does this mean we have to know which vectors are in the finite set $ L \cap \mathbb{Z}^n_{Dq}$?" No, that's not how "quantum parallelism" works. In the same way that preparing a state $\sum_i|i\rangle|f(i)\rangle$ for some efficiently computable $f$ doesn't mean we "know" or have a list of all the values $f(i)$. It's in superposition, measuring w.r.t. the computational basis will reveal one value probabilistically. Determining membership $\mathbf{v} \in L \cap \mathbb{Z}^n_{Dq}$ is efficiently computable (although we can't do it efficiently for exponentially many vectors). $\endgroup$
    – yoyo
    Apr 17 at 1:37
  • 2
    $\begingroup$ @yoyo: On the other hand, if we were able to generate such a quantum state and then measure it, that would measure as a random vector in the state (with the probability of each one being dictated by the amplitude). If we have a good probability of that giving us a short vector, well, if we repeat this a number of times, wouldn't this give us a short vector basis? And, even if that isn't enough to immediately solve the LWE problem, wouldn't that be enough to make it easier? Or, am I completely misunderstanding the Quantum State? $\endgroup$
    – poncho
    Apr 17 at 18:38
  • 1
    $\begingroup$ @poncho "If we have a good probability of that giving us a short vector" is the key. The quantum algorithms I'm familiar with will start with a uniform superposition over some state space; the magic (in addition to quantum parallelism i.e. linearity) is manipulating the probabilities/amplitudes so that you get something meaningful upon measurement with non-negligible probability. E.g. with factoring you can apply modular exponentiation "in parallel" then the QFT (FFT "in parallel") detects periodicity in that it piles up the amplitudes near meaningful output. $\endgroup$
    – yoyo
    Apr 17 at 18:52
  • 2
    $\begingroup$ @yoyo: well, if I look at the target Quantum State, it would appear to give much larger amplitude to short vectors (if I understand the $\exp \left(\frac{- \pi i ||\mathbf{y}||^2}{s^2} \right)$ part correctly). If so, isn't Wenzhe observation "how do you give such larger amplitudes to short vectors", which (as you point out) isn't a fall-out from the standard uniform superposition procedure)? $\endgroup$
    – poncho
    Apr 17 at 18:56
  • $\begingroup$ I do not understand what you mean @poncho, is the question here not about the left hand side of the tensor product, i.e., how to efficiently prepare the superposition $\sum_{\mathbf{v} \in L \cap \mathbb{Z}^n_{Dq}} |\mathbf{v} \rangle$? Maybe I misunderstand what you mean by the target state. Unless the question how this superposition is efficiently prepared is answered elsewhere in the paper, I think it is odd that it is not commented on in the paper and then no one has pointed out how to do it here for two days for this high profile question. $\endgroup$
    – erth
    Apr 18 at 10:06
11
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ I never knew that when I reviewed first drafts of papers and found statements that needed more thought and attention that I was "invalidating" the paper. I feel so much more important now. $\endgroup$
    – duckstar
    Apr 16 at 3:39
  • 3
    $\begingroup$ Yilei Chen has now addressed this on his webpage (chenyilei[dot]net) $\endgroup$
    – integrator
    Apr 16 at 9:46
  • 8
    $\begingroup$ Note that the author said this was fixed and that he forgot to update a lemma chenyilei.net $\endgroup$ Apr 16 at 9:49
8
$\begingroup$

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.

Post by Yilei Chen

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.

$\endgroup$

Your Answer

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

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