A potential tectonic shift is brewing in the world of cryptography. Daniel Simon, a researcher at Amazon Web Services (AWS), has presented the scientific community with a new quantum algorithm that, if confirmed, could radically change our understanding of the security of lattice-based cryptosystems, which underpin modern post-quantum standards. This is not about an immediate break, but a theoretical breakthrough that calls into question the very mathematical foundation of future security.
Simon, known for his eponymous algorithm from the 1990s, which became a precursor to the famous Shor's algorithm, has focused his new work on the Dihedral Coset Problem (DCP). This mathematical problem is not directly used for encryption, but it is the key to solving other, more complex problems on which lattice-based cryptography is built. In the early 2000s, mathematician Oded Regev proved that an efficient solution to DCP opens the way to attacks on certain variants of problems on high-dimensional lattices, but his approach required an idealized tool that did not exist. Simon claims to have found a way to bypass this limitation by performing the necessary transformations directly on a quantum computer.
The essence of the threat: from theory to practice
The claimed algorithm, according to the author, solves problems not exponentially but polynomially, meaning its runtime grows as a power of the problem size, rather than as an exponential function. Combined with Regev's work, this potentially extends to fundamental problems such as the Shortest Vector Problem (SVP) and Learning With Errors (LWE). It is on structured variants of LWE, such as Module-LWE, that the standards of the U.S. National Institute of Standards and Technology (NIST) are built, including the ML-KEM key encapsulation mechanism and the ML-DSA digital signature algorithm, standardized in 2024.
However, it is crucial to remain calm. This preprint does not contain a practical attack on current standards. Simon does not demonstrate the recovery of ML-KEM keys or the forgery of ML-DSA signatures with real security parameters. Moreover, LWE is a whole family of problems, and a result for one class cannot be automatically transferred to all structured variants used in the industry. The document also lacks an assessment of the required resources—the number of logical qubits, quantum gates, and the volume of error correction—which makes it far from practical implementation.
Caution above all
History knows examples of loud claims that did not withstand scrutiny. In 2024, researcher Yilei Chen already announced a polynomial quantum algorithm for LWE, but a few days later, a fatal error was found in his proof, and he withdrew his conclusion. This case is a stark reminder that in quantum cryptography, multiple verifications of results are necessary. At the moment, there is no independent expert consensus on Simon's work, and this is the main factor of uncertainty.
My analysis: This publication is not a signal for panic or a reason for immediate migration, but an important wake-up call for the entire crypto community. It highlights that even the most reliable mathematical constructions to date can be vulnerable to new theoretical breakthroughs. The industry needs not only to implement post-quantum standards but also to actively fund research in quantum resilience and develop hybrid schemes to be ready for any scenario. We are on the threshold of a new era where the line between theory and practice is becoming increasingly thin.