According to Chen’s paper https://eprint.iacr.org/2024/555.pdf, LWE based encryption schemes are now vulnerable to quantum machines. If it is the situation then is this the end of homomorphic encryption schemes that are based on LWE problems?
The answer to my question came from Nigel Smart (https://nigelsmart.github.io/LWE.html):
“…
So it would appear that the attack should apply to BGV.
…
Thus the attack would need to improve quite a bit to apply to TFHE.
…”
Briefly, that is the answer. BGV/BFV/CKKS have a relation between n and q that is more similar to what the paper claims that can be broken by quantum computers with the proposed polynomial-time algorithm, while FHEW/TFHE, as well Kyber and Dilithium, have a relation between n and q not captured yet by the attack.
Of course the above is relevant only if we make the assumption that the attack is correct, and ignore all constants and extra costs incurred by quantum algorithms. We have yet to see the results of the peer review.
1 Like
The following note has been added to the paper:
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.
1 Like