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
back
1 comments
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.