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 |