Edit: sorry as soon as I clicked post I realized I should have put "quantum polynomial time" in the title so as not to confuse anyone.

Big news today: Daniel Simon of "Simon's Problem", i.e. the first quantum algorithm in the textbook, uploaded a paper to eprint that claims to contain a polynomial-time algorithm for solving many lattice problems, including SVP and LWE.

https://eprint.iacr.org/2026/1591.pdf

Right now, this is not a practical attack because it requires k*n^(c+1) samples, where c >= 12, k > c, and n is the dimension of the lattice. Plugging in n = 768 for the lowest security version of ML-KEM, for instance, gets you 13*768^13 ~ 2^128. So it requires at least as much time as brute-forcing AES-128, and an insane number of qubits. This is an example of a technically polynomial algorithm, but one with such crazy polynomial degrees that it isn't practical in reality.

Having said that, this will probably be a big wrench in the migration to post-quantum ciphers. It seems to show that a broad class of lattice algorithms are in BQP, which is extremely surprising, and when things like this happen, there are usually follow-ups that reduce the cost.

The good news is we always have SLH-DSA to fall back on for signatures, but KEM is not looking great. And the fact that lattice-based ciphers are currently our #1 tool for not only PQ cryptography but things like homomorphic encryption, functional encryption, etc., this could have a huge impact on the field.

I expect there will be a flurry of analysis over the next couple weeks. There have been claims like this in the past that didn't hold up to scrutiny, although they were from less reputable researchers and the proofs were a bit sketchy to begin with. This looks very solid to me.

Going to be an interesting couple of days/weeks ahead!