Amazon Web Services (AWS) researcher Daniel Simon presented a new quantum algorithm that could significantly speed up solving some of the mathematical problems underpinning post-quantum cryptography.
He says the algorithm’s runtime grows as a power of the problem size rather than exponentially. If confirmed, the result could change views on the resistance of certain problems to quantum computing. The paper does not include a practical attack on current standards, including ML-KEM and ML-DSA.
In the 1990s, Simon developed Simon’s algorithm, one of the first examples of a significant quantum advantage and a precursor to Shor’s algorithm.
In the new work, the researcher examines a mathematical problem called the Dihedral Coset Problem (DCP). Roughly, a quantum computer receives a set of related states and must determine a hidden value among them.
DCP itself is not used to protect crypto wallets or internet connections. It matters because mathematicians have proven its connection to other problems whose hardness underpins lattice cryptography.
In the early 2000s, Oded Regev showed that an efficient algorithm for DCP can be used to solve certain variants of lattice problems. However, the known polynomial approach required an idealized tool for solving another hard computational problem.
Simon says he was able to bypass this limitation. His algorithm is supposed to perform the required transformation directly on a quantum computer.
The result affects the foundations of post-quantum cryptography
Combined with previous mathematical work, Simon’s algorithm potentially applies to certain variants of the Shortest Vector Problem (SVP) and Learning With Errors (LWE).
SVP can be thought of, in simplified terms, as finding a sufficiently short path between points in a highly complex high-dimensional structure. LWE hides a secret in a system of equations with intentionally added “noise.”
Existing computers cannot efficiently solve certain variants of these problems at sufficiently large parameters. It is believed that future quantum machines also should not be able to, which is why a significant part of post-quantum cryptography is built on lattice mathematics.
In 2024, the U.S. National Institute of Standards and Technology (NIST) standardized the ML-KEM key encapsulation mechanism. Its security is tied to the hardness of Module Learning With Errors, a structured variant of LWE.
The digital signature standard ML-DSA also belongs to lattice cryptography and uses related mathematical problems. If Simon’s result is confirmed, it would show that a quantum computer can, in principle, solve some problems related to this area substantially more efficiently than previously thought.
ML-KEM has not been broken
The study does not imply that a quantum computer can now recover an ML-KEM key or forge an ML-DSA signature. Simon did not attack a specific cryptographic standard or show a way to break its real-world parameters. The work concerns mathematical problems and certain variants of their solution.
LWE is a family of problems. Practical post-quantum cryptography uses specially structured variants, so a result for one class of LWE cannot be automatically transferred to any cryptographic system based on it.
The preprint also does not estimate the number of logical qubits, quantum gates, or error-correction operations needed to run the algorithm at cryptographically meaningful sizes. As of publication, there is no independent expert consensus on the study.
There have been cases in this field where high-profile preliminary results did not withstand scrutiny. In 2024, researcher Yilei Chen claimed a polynomial-time quantum algorithm for LWE and related lattice problems. Within days, specialists found a flaw in a key part of the proof, after which the author withdrew the main conclusion.
In May, Quantus developers said that a significant part of the crypto industry depends on algorithms vulnerable to potential quantum attacks and that a transition to post-quantum solutions is needed.
For more on whether you can profit from quantum technologies, how blockchains are preparing for the ‘quantum’ era, and whether the quantum internet can really be hacked, see the new “Quantum & After” section.
