An AWS quantum algorithm challenges the foundation of post-quantum cryptography
The scientific community has been shaken by a new work from Daniel Simon, a researcher at Amazon Web Services. The quantum algorithm he presented, according to preliminary estimates, is capable of radically accelerating the solution of a number of mathematical problems on which modern post-quantum cryptography is based. The key thesis is that the algorithm's time complexity grows not exponentially, but polynomially, which, if confirmed, will overturn current ideas about the resistance of lattice constructions to quantum attacks.
It is important to emphasize: the document contains neither a practical attack on current standards like ML-KEM and ML-DSA, nor even a theoretical break of their real parameters. Simon's work, known for his eponymous algorithm of the 90s — a predecessor to the famous Shor's algorithm — focuses on a more abstract problem known as the Dihedral Coset Problem (DCP).
The essence of the mathematical breakthrough
DCP is not directly used to protect wallets or connections, but it is a cornerstone for lattice cryptography. Back in the early 2000s, Oded Regev proved that an efficient solution to DCP would allow attacking certain variants of problems on high-dimensional lattices. However, his approach ran into the need to use an idealized, non-existent tool for another complex computational operation. Simon claims to have found a way to bypass this limitation by performing the required transformation directly on a quantum computer.
In combination with earlier works, this algorithm potentially extends to variants of the Shortest Vector Problem (SVP) and Learning With Errors (LWE). To simplify, SVP is the search for the shortest vector in a complex high-dimensional lattice, and LWE is the recovery of a secret from a system of equations with deliberately added "noise." It is on the complexity of these problems that the NIST standards adopted in 2024 are built: the ML-KEM key encapsulation mechanism and the ML-DSA digital signature algorithm.
Panic is premature
Despite the loud headlines this news might generate, I urge caution. The research does not demonstrate a break of ML-KEM or forgery of an ML-DSA signature. Moreover, LWE is a whole family of problems, and practical standards use specially structured subtypes of them. A result for one class of LWE cannot be automatically transferred to all cryptographic systems.
The preprint lacks critically important information: an estimate of the number of logical qubits, quantum gates, and the volume of error correction required to run the algorithm at cryptographically significant sizes. Without this data, it is too early to talk about a practical threat. History knows examples where loud claims crumbled to dust — as in 2024, when researcher Yilei Chen claimed a polynomial algorithm for LWE, but a few days later a fatal error was found in his proof.
My analysis: This work is an important intellectual challenge that underscores that our understanding of quantum computing is still in a formative stage. However, for the industry, it is more of a signal to accelerate the transition to hybrid schemes and diversify cryptographic primitives than a reason for panic. We are likely still far from the practical implementation of a quantum break of NIST standards, but ignoring such theoretical breakthroughs would be the height of frivolity.