Polynomial-Time Quantum Algorithm Proposed for Lattice-Based Cryptography [pdf]
1–4 of 4 posts
Re: Polynomial-Time Quantum Algorithm Proposed for Lattice-Based Cryptography [pdf]
#2If 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
Re: Polynomial-Time Quantum Algorithm Proposed for Lattice-Based Cryptography [pdf]
#3If 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 ?
Re: Polynomial-Time Quantum Algorithm Proposed for Lattice-Based Cryptography [pdf]
#4If 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.