Daniel Simon, a researcher at Amazon Web Services (AWS), has introduced a new quantum algorithm that may significantly accelerate the resolution of certain mathematical problems underpinning post-quantum cryptography.
According to Simon, the algorithm's runtime increases polynomially rather than exponentially with the size of the task. If validated, this could reshape our understanding of the resilience of certain problems against quantum computing. However, the paper does not present a practical attack on existing standards, including ML-KEM and ML-DSA.
In the 1990s, Simon developed a quantum algorithm that bears his name, which became one of the first examples showcasing a significant advantage of quantum computation and served as a precursor to Shor's algorithm.
In his latest work, Simon examines a mathematical challenge known as the Dihedral Coset Problem (DCP). In simplified terms, a quantum computer receives a set of entangled states and must identify a hidden value among them.
While DCP itself is not utilized to secure crypto wallets or internet connections, it is crucial because mathematicians have established its connection to other problems that form the basis of lattice-based cryptography.
In the early 2000s, Oded Regev demonstrated that an efficient algorithm for DCP could solve specific variants of problems related to high-dimensional lattices. However, the existing polynomial approach required an idealized tool to tackle another complex computational problem.
Simon claims to have overcome this limitation, stating that his algorithm performs the necessary transformation directly on a quantum computer.
Implications for Post-Quantum Cryptography
When combined with previous mathematical research, Simon's algorithm potentially extends to certain variations of the Shortest Vector Problem (SVP) and Learning With Errors (LWE).
SVP can be simply described as the task of finding a relatively short path between points within a highly complex multidimensional structure. LWE conceals a secret within a system of equations that has been intentionally distorted with mathematical "noise."
Current computers struggle to efficiently solve specific variants of these problems at sufficiently large parameters. It is believed that future quantum machines will also be unable to tackle them, which is why a significant portion of post-quantum cryptography relies on lattice-based mathematics.
Specifically, in 2024, the U.S. National Institute of Standards and Technology (NIST) standardized the ML-KEM key encapsulation mechanism, with its security tied to the complexity of Module Learning With Errors—a structured variant of LWE.
The ML-DSA digital signature standard is also based on lattice cryptography and employs related mathematical problems. If Simon's findings are confirmed, it would indicate that certain related problems could be solved by quantum computers significantly more efficiently than previously thought.
ML-KEM Remains Secure
It is important to note that the research does not imply that a quantum computer can now recover the ML-KEM key or forge an ML-DSA signature. Simon did not attack a specific cryptographic standard nor did he demonstrate a method to compromise its actual parameters. The work pertains to mathematical problems and specific variants of their solutions.
Additionally, LWE encompasses an entire family of problems. In practical post-quantum cryptography, specially structured variants are employed, meaning that results for one class of LWE cannot be automatically applied to any cryptographic system based on it.
The preprint also lacks an assessment of the number of logical qubits, quantum gates, or error correction operations necessary to implement the algorithm at cryptographically significant sizes. As of the publication date, there is no independent expert consensus on the research.
This field has previously seen cases where high-profile preliminary results failed to withstand scrutiny. In 2024, researcher Yilei Chen announced a polynomial quantum algorithm for LWE and related lattice problems, only for experts to discover an error in a key part of the proof shortly after, leading the author to retract the main conclusion.
As a reminder, in May, developers at Quantus highlighted the reliance of a significant portion of the crypto industry on algorithms vulnerable to potential quantum attacks, emphasizing the need to transition to post-quantum solutions.
For insights on whether one can profit from quantum technologies, how blockchains are preparing for the "quantum" era, and the feasibility of hacking the quantum internet, check out our new section "Quantum & After."