Quantum threat to post-quantum cryptography: AWS algorithm calls into question the resilience of lattice standards
A potentially tectonic shift is brewing in the world of cryptography. My analysis of a new preprint presented by Amazon Web Services researcher Daniel Simon has revealed a quantum algorithm that could radically accelerate the solution of mathematical problems underlying post-quantum cryptography. This is not just a theoretical curiosity — it is a direct challenge to established notions about the security of modern standards.
Simon's key innovation lies in the fact that his algorithm demonstrates a polynomial, rather than exponential, dependence of runtime on problem size. If this result passes independent verification, we will have to reconsider the very paradigm of lattice cryptosystems' resistance to quantum computing. However, it is important to emphasize: this is not a practical attack on current standards such as ML-KEM or ML-DSA, but rather a theoretical breakthrough pointing to potential vulnerabilities.
Simon, known for his eponymous algorithm from the 1990s that became a precursor to the famous Shor's algorithm, focused in his new work on the Dihedral Coset Problem (DCP). At first glance, DCP is not directly used to protect wallets or connections, but it is precisely the link to more complex problems in lattice cryptography. Back in the early 2000s, Oded Regev proved that an efficient solution to DCP would open the way to breaking certain variants of problems on multidimensional lattices, but at that time it required an unattainable idealized tool.
Simon claims to have circumvented this limitation by performing the necessary transformation directly on a quantum computer. Combined with previous works, his algorithm potentially extends to the key problems of the Shortest Vector Problem (SVP) and Learning With Errors (LWE). It is on the complexity of these problems that the security of the NIST standards adopted in 2024, including ML-KEM and ML-DSA, is built. If the algorithm is confirmed, it would show that quantum computers are theoretically capable of solving these problems significantly more efficiently than previously assumed.
Panic is premature, but vigilance is mandatory
Nevertheless, I would not advise the market to panic. Simon's work does not demonstrate a way to recover ML-KEM keys or forge ML-DSA signatures at real-world parameters. LWE is a whole family of problems, and practical standards use their structured variants, so a result for one class does not automatically transfer to all systems. Moreover, the preprint lacks an assessment of the required resources — logical qubits, gates, and error correction — for an attack on cryptographically significant sizes. History knows examples where loud claims collapsed: in 2024, researcher Yilei Chen already announced a polynomial algorithm for LWE, but his proof contained an error, and he retracted his conclusions.
My professional verdict: this preprint is not a reason for immediate migration, but a serious signal for the crypto industry. We stand on the threshold of an era where theoretical research can quickly transform into real threats. Projects dependent on long-term security should already be building flexibility into their roadmaps to transition to new, potentially more resilient cryptographic primitives, rather than waiting for the "quantum fracture" to become a fait accompli.