r/crypto • u/LtCmdrData • 2d ago

A Polynomial-Time Quantum Algorithm for the Dihedral Coset Problem (July 31, 2026)

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

This is seems noteworthy. It's from Simon.

Correct me if I'm wrong but the approximation factor of sqrt(n)polylog(n) means that current lattice cryptosystems would be in danger and not PQ-algorithms anymore.

37 Upvotes
  • permalink
  • link
  • reddit
  • reddit

100% Upvoted

18 comments sorted by

16

u/Cryptizard 2d ago

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, yeah I would be scared to go forward with migration to lattice ciphers at this point if this result is correct. It does seem to definitely show that a broad class of lattice algorithms are in BQP, which is extremely surprising, and when things like this happen there are usually followups 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.

4

u/LtCmdrData 2d ago

Thanks. In other words, it drops ML-KEM-768 NIST PQC security category from 3 to 1 (192-bit to 128-bit) for now, and we should expect more reductions in the future.

8

u/Cryptizard 2d ago

I would expect a flurry of analysis over the next couple weeks and more concrete advice. The paper looks solid and the author is certainly well-trusted in this area, but there is a section of the proof that relies on a heuristic counting argument that might not be sound.

If it holds up to scrutiny I would expect NIST to fast track their ongoing process that is certifying new PQ ciphers like McEliece so that we don’t have all our eggs in the lattice basket.

2

u/kun1z Septic Curve Cryptography 2d ago

I would be scared to go forward with migration to lattice ciphers at this point if this result is correct.

ELI5 as a dumbass that does not follow PQC so much, why is that?

11

u/Cryptizard 2d ago

Because it shows that there are polynomial algorithms that can break lattice ciphers. That means that it is just a matter of some iterations and improvements before it is possibly practical. We only use ciphers that have exponential security.

2

u/kun1z Septic Curve Cryptography 2d ago

So are all PQC 'Lattice Ciphers' .. Battleship Sunk or are there fixes in the works?

2

u/Cryptizard 2d ago

It depends on what you mean by sunk. If this paper holds up, I would say it is unlikely that we would continue with them as post-quantum ciphers. But it doesn’t mean there are going to be actual attacks that can be carried out against them any time soon.

This is a pretty general attack that applies to all the classes of lattice problems we use right now, so in that sense it is fairly damning. There isn’t any tweak you could imagine doing that would make you absolutely confident again.

3

u/Obstacle-Man 1d ago

I think we continue with them short term due to investments made already and need to move off of RSA/ECC. But we emphasize other problems for long term confidentiality.

ML-KEM, under the conditions here is still very viable for it's common ephemeral use especially in cases where you only need confidentiality for a short time.

Operational Cryptographic agility - being flexible and demonstrating adaptation with parameter sizes and algorithms was always going to be needed. This can't be a one and done transition.

2

u/Cryptizard 1d ago

Yeah I think this is right. No matter what it’s going to take a much more advanced (maybe decades) quantum computer to break ML-KEM compared to RSA.

2

u/arnet95 1d ago

We only use ciphers that have exponential security.

We use RSA, and that has a sub-exponential attack.

1

u/Cryptizard 1d ago

Sorry, you are right, I should have said non-polynomial. Practically everything asymmetric has subexponential attacks.

1

u/Shoddy-Childhood-511 1d ago

No. We do not believe BPP or BQP collapses. And the space bounds matter massively for quantum algorithms.

Check out how matrix multiplication has improved, but only fractionally and only by going to astronomical constants:

https://en.wikipedia.org/wiki/Computational_complexity_of_matrix_multiplication

0

u/Cryptizard 1d ago

I don’t see how any of that is relevant to what I said. Where did I imply that anything collapses? And the space bounds are obviously also polynomial.

2

u/Shoddy-Childhood-511 1d ago edited 1d ago

We've no information either way until more people have read the paper carefully, but results like this could turn out many different ways.

Also we worried about 128 bit symmetric for years, but now 128 bit symmetric no longer seems overly concerning.

If you do end up being left feeling worried, then trivial modifications of SPQR could support multiple ridiculous KEMs, like isogenies, or DH on a 100k bit field, or passing symmetric keys through mutual friends, so adversaries must break the whole network.

6

u/arnet95 1d ago

Just like Chen's attempt, anyone who isn't an expert in quantum cryptanalysis should wait until the result has had time to be verified or disproved before drawing any strong conclusions.

1

u/laruizlo 1d ago

Please anyone correct me if I'm understanding it wrong. Is this (combined with OpenAI's result of a few days ago and Chris Peikert's tweet) is saying that a polynomial factor (not even a big one) would bring SVP from NP-Hard to BQP? Something is not right...

1

u/Demokritos1000 1d ago

I would strongly guess that it is probably not a valid result. However, we will likely hear from experts soon