Polynomial-Time Quantum Algorithm Proposed for Lattice-Based Cryptography [pdf]archive.cr.yp.to 5 pointsnamjh1 month ago3 commentsSaveHideCopy link On HNComments−u1hcw9nx1moIf that result holds, ML-KEM, FALCON, FHE schemes would all stop being PQ algorithms. Back to the drawing board.ps. The author seems to be Simon's problem Simon https://en.wikipedia.org/wiki/Simon%27s_problem−SuchAnonMuchWow1moI though LWE and SVP were NP-hard. Doesn't breaking them mean NP is in BQP, and thus classical computer encryption is entirely broken with quantum computers ?How would we recover from this back to the drawing board ?−u1hcw9nx1moExact SVP is NP-hard, but LWE is not. Kyber/ML-KEM and Dilithium/ML-DSA) rely on approximate lattice problems, not exact ones.
Comments
If that result holds, ML-KEM, FALCON, FHE schemes would all stop being PQ algorithms. Back to the drawing board.
ps. The author seems to be Simon's problem Simon https://en.wikipedia.org/wiki/Simon%27s_problem
I though LWE and SVP were NP-hard. Doesn't breaking them mean NP is in BQP, and thus classical computer encryption is entirely broken with quantum computers ?
How would we recover from this back to the drawing board ?
Exact SVP is NP-hard, but LWE is not. Kyber/ML-KEM and Dilithium/ML-DSA) rely on approximate lattice problems, not exact ones.