Daniel Simon’s Dihedral Coset Algorithm: What Does It Actually Mean for Lattice-Based Cryptography and PQC?
- Brian Couzens
- Aug 9
- 5 min read
A new preliminary paper from Daniel R. Simon has generated exactly the sort of reaction that serious cryptographic research does not need.
“Another horror for lattice-based cryptography.”
“This is the end for PQC.”
Neither statement is an adequate description of what has actually been published.
The paper is potentially extremely important. It is also a preliminary research result, and the distinction matters.
Simon’s paper, “A Polynomial-Time Quantum Algorithm for the Dihedral Coset Problem”, proposes a polynomial-time quantum algorithm for the Dihedral Coset Problem (DCP), together with consequences for lattice problems and Learning With Errors (LWE).
The paper is available through the IACR Cryptology ePrint Archive:
The correct response is neither panic nor dismissal.
It is analysis.
Why the Dihedral Coset Problem matters
The Dihedral Coset Problem is not an obscure mathematical curiosity disconnected from post-quantum cryptography.
There is a long-established relationship between DCP, lattice problems and LWE.
Regev demonstrated a quantum connection between the Dihedral Coset Problem and lattice problems. Subsequent work established deeper relationships between LWE and the Extrapolated Dihedral Coset Problem (EDCP), a generalisation of DCP.
That relationship matters because LWE sits underneath a substantial portion of modern lattice-based cryptography.
ML-KEM, the NIST standard derived from Kyber, is based on Module-LWE.
Consequently, progress against problems related to DCP deserves serious attention.
But this is where commentary frequently goes wrong.
A mathematical relationship between problems does not mean that an algorithm for one problem automatically becomes an operational attack against every cryptographic construction associated with another.
The reductions matter.
The parameters matter.
The assumptions matter.
The exact problem being solved matters.
And the implementation consequences matter.
What Simon is actually claiming
At a high level, Simon claims a polynomial-time quantum algorithm for DCP under conditions involving faulty samples.
The paper then derives consequences for lattice problems and certain LWE instances.
That is potentially a major development.
Historically, the difficulty of obtaining an efficient quantum algorithm for DCP has been an important barrier in this area.
Kuperberg's well-known quantum algorithms gave subexponential approaches to related dihedral hidden-subgroup problems, but that is very different from a polynomial-time algorithm.
Earlier research has also produced polynomial-time quantum algorithms for particular variants of LWE, SIS and EDCP.
But there is an important recurring qualification in that literature: solving a specially parameterised variant is not necessarily equivalent to solving the standard cryptographic problem.
For example, Chen, Liu and Zhandry explicitly noted that their polynomial-time results for particular variants of SIS, LWE and EDCP did not place standard lattice-based cryptography at risk because the solved variants were outside the parameter regimes known to inherit the relevant worst-case hardness relationships.
More recently, work on quasi-polynomial quantum algorithms for EDCP over power-of-two moduli explicitly stated that the result did not affect standard LWE parameters because of the sample limitations in the reduction.
That history is important.
It gives us the correct question to ask about Simon's result.
The question is not “Is PQC dead?”
The question is:
Does Simon's polynomial-time DCP algorithm actually propagate through the relevant reductions into the parameter regimes underlying cryptographically deployed LWE and Module-LWE schemes?
That is a much harder question.
The chain we need to examine is roughly:
DCP algorithm
↓
DCP assumptions and parameter regime
↓
valid reduction
↓
LWE
↓
cryptographically relevant LWE parameters
↓
Module-LWE / Ring-LWE relationships where applicable
↓
ML-KEM and other deployed lattice-based constructions
Only when that chain has been established can we responsibly move from “important theoretical result” to “practical cryptographic consequence”.
That distinction is not semantic.
It is the entire issue.
What would make this genuinely serious?
There are several possibilities.
If Simon's algorithm survives independent scrutiny and genuinely provides a polynomial-time quantum solution to DCP in the regime required by the relevant reductions, that would represent a significant change in the theoretical landscape.
If those reductions then reach standard cryptographic LWE parameters, the consequences become considerably more serious.
And if those consequences extend to the assumptions and structures used by deployed Module-LWE schemes such as ML-KEM, then the PQC community would have a genuine problem to solve.
That would not be a minor security-level adjustment.
It would require a reassessment of a foundational assumption behind a major family of post-quantum cryptographic constructions.
But we are not entitled to skip those steps.
A preliminary paper is not a cryptographic break
This is where some of the commentary surrounding the paper has already gone off the rails.
Calling it “another horror for lattice-based cryptography” implies that a previous sequence of demonstrated catastrophes has now been joined by another one.
That is not what the paper establishes.
Likewise, declaring “the end of PQC” is an extraordinary claim that requires extraordinary evidence.
The paper does not, simply by existing, demonstrate:
a practical attack against ML-KEM;
recovery of ML-KEM private keys;
a break of Module-LWE at deployed parameters;
a polynomial-time attack against deployed PQC implementations;
a practical quantum computer capable of running the proposed algorithm;
or the collapse of lattice-based cryptography as a whole.
Those are separate claims requiring separate evidence.
That does not diminish the importance of Simon's work.
It makes the work worth examining properly.
This is why cryptographic commentary needs discipline
We have already seen how rapidly a technically nuanced development can become distorted on social media.
A scheme is withdrawn and suddenly “PQC is failing”.
A new quantum algorithm appears and suddenly “lattice cryptography is finished”.
A theoretical improvement is published and suddenly someone announces the apocalypse.
This is not useful.
HAWK, for example, was a legitimate development that deserved careful examination. It did not justify declaring post-quantum cryptography finished.
The same principle applies here.
The appropriate response to Simon's paper is neither “nothing to see here” nor “PQC is dead”.
It is:
Read the paper.
Understand the theorem.
Examine the algorithm.
Check the assumptions.
Follow the reductions.
Check the parameters.
Determine what happens when the theory meets actual cryptographic constructions.
Then draw the conclusion.
What we are watching
For organisations already planning or executing post-quantum cryptographic migration, this distinction is particularly important.
Nothing in a preliminary theoretical result justifies stopping migration.
Quite the opposite.
Cryptographic agility exists precisely because cryptographic assumptions can change.
A serious organisation should already know:
Which algorithms it uses.
Where they are used.
Which systems depend upon them.
Which data they protect.
Which certificates, keys and signatures depend upon them.
Which cryptographic assumptions underpin those mechanisms.
And how quickly those dependencies can be changed if the underlying security position deteriorates.
That is cryptographic resilience.
It does not depend on pretending that today's algorithms are invulnerable.
Nor does it depend on declaring every new academic paper a catastrophe.
The conclusion
Daniel Simon's paper deserves attention.
Potentially, it deserves a great deal of attention.
A polynomial-time quantum algorithm for DCP would be an important theoretical development, particularly because of the established relationship between DCP, lattice problems and LWE.
But the responsible conclusion today is not:
“Lattice cryptography is finished.”
Nor is it:
“This is the end of PQC.”
The responsible conclusion is:
A potentially important new result has appeared. Now we need to determine exactly how far it travels.
The decisive issue is whether the claimed result survives independent scrutiny and whether its reductions reach the cryptographically relevant parameter regimes used by modern lattice-based cryptography.
That is the work that matters.
Not the headline.
Not the outrage.
Not the engagement bait.
The mathematics.
And until the mathematics has been independently tested, anyone announcing either the death of lattice cryptography or the death of PQC is getting considerably ahead of the evidence.
Primary source
The broader literature is equally important. Earlier work establishes the DCP/LWE/lattice connections, while previous polynomial-time and quasi-polynomial results demonstrate why parameter regime and reduction details are not footnotes but the central issue. (IACR Eprint Archive)
Comments