Polynomial-Time Quantum Algorithm Proposed for Lattice-Based Cryptography [pdf]

archive.cr.yp.to

5 pointsnamjh3 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.

Reply on news.ycombinator.com