zama-ai/tfhe-rs

Please add a note about the impact of "Polynomial-time Quantum Algorithms for Lattice Problems" (if it holds up) on TFHE implementations

jayavanth opened this issue · 1 comments

What is the problem you want to solve and can not with the current version?
Wanted to know how the work in this paper would impact software that was built using TFHE libraries like this one

The algorithm has a bug and so it is invalid.

Note: 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.