Update on "Quantum Algorithms for Lattice Problems"

Recently, Yilei Chen reported an attack on a post-quantum cryptography primitive: Learning With Errors (LWE), a hard problem on lattices.[1]

Hongxun Wu and Thomas Vidick found a bug in the paper which invalidates the attack:

> Update on April 18: Step 9 of the algorithm contains a bug, which I don’t know how to fix. See 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. [2]

[1] https://news.ycombinator.com/item?id=39998396

[2] https://eprint.iacr.org/2024/555