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

Polynomial-Time Quantum Algorithm Proposed for Lattice-Based Cryptography [pdf](archive.cr.yp.to)

5 points by namjh 15 days ago | 3 comments

u1hcw9nx 15 days ago |

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 ?

u1hcw9nx 14 days ago | | |

Exact SVP is NP-hard, but LWE is not. Kyber/ML-KEM and Dilithium/ML-DSA) rely on approximate lattice problems, not exact ones.