The world of post-quantum security has been shaken by a fresh scientific paper presented by Amazon Web Services (AWS) researcher Daniel Simon. In a new preprint, he describes a quantum algorithm that, he claims, can solve key mathematical problems underlying modern post-quantum standards with polynomial complexity—meaning its runtime grows as a power of the problem size, rather than exponentially, as previously thought.
If this result proves correct, it could radically reshape our understanding of lattice-based cryptography's resilience to quantum computing. However, it is important to emphasize: the document does not contain a practical attack on current standards such as ML-KEM (key encapsulation mechanism) or ML-DSA (digital signatures). This is about a theoretical breakthrough that has yet to be verified.
The essence of the algorithm and its connection to lattices
Simon, known for his eponymous algorithm from the 1990s, which became a precursor to the famous Shor's algorithm, has focused in his new work on the so-called Dihedral Coset Problem (DCP). Simplified, a quantum computer receives a set of correlated states and must identify a hidden value between them. DCP itself is not directly used for encryption, but back in the early 2000s, mathematician Oded Regev proved that an efficient solution to DCP would allow attacking certain variants of problems on high-dimensional lattices, including the Shortest Vector Problem (SVP) and Learning With Errors (LWE).
The main limitation of Regev's approach was the need for an idealized tool to solve another complex problem. Simon claims he has managed to bypass this obstacle by performing the necessary transformation directly on a quantum computer. This potentially opens the way to accelerated solving of structured variants of LWE, on which the NIST standards adopted in 2024 are built.
Panic is premature: what remains behind the scenes
Despite the loud headlines, Simon's work does not demonstrate a break of ML-KEM or forgery of ML-DSA signatures. The researcher did not attack specific cryptographic parameters, and his algorithm does not include estimates of the number of logical qubits, quantum gates, or error correction operations needed for practical implementation. Moreover, LWE is a whole family of problems, and a result for one class does not automatically transfer to all structured variants used in the industry.
In the scientific community, there have already been precedents where loud claims of polynomial quantum algorithms for lattices failed verification. For example, in 2024, researcher Yilei Chen claimed a similar breakthrough, but a few days later a fatal error was found in his proof, and he retracted his conclusions. Currently, there is no independent consensus on Simon's work, and this is the main indicator that conclusions are premature.
My analysis: This preprint is an important signal for the industry, but not a reason for panic. It highlights the fragility of our current theoretical security models. Even if Simon's algorithm turns out to be correct, practical threat is decades away. However, the crypto community should accelerate the transition to hybrid schemes and diversification of post-quantum algorithms, so as not to place all security on a single mathematical foundation.