Daniel Simon, a researcher at Amazon Web Services (AWS), has published a paper in which he introduced a new quantum algorithm. This algorithm potentially makes it possible to speed up the solution of certain mathematical problems underlying post-quantum cryptography. According to the author, the running time of the algorithm increases proportionally to the degree of the problem size, and not exponentially. It is worth noting that the document does not describe a practical attack on existing cryptographic standards such as ML-KEM and ML-DSA.

The study examines the mathematical problem of the Dihedral Coset Problem (DCP). Previously, mathematicians, including Oded Regev, proved the connection of DCP with problems on multidimensional lattices. Simon claims that his algorithm allows performing the necessary transformation directly on a quantum computer, bypassing the limitations of previous polynomial approaches that required idealized computational tools. This result potentially extends to the variants of the Shortest Vector Problem (SVP) and Learning With Errors (LWE) tasks. These tasks are the foundation for many post-quantum cryptographic systems, including the ML-KEM and ML-DSA mechanisms, standardized by the National Institute of Standards and Technology (NIST) in 2024.

The authors emphasize that the current results do not mean that ML-KEM standards have been hacked or ML-DSA signatures have been forged. Practical post-quantum cryptography uses specific structured variants of LWE tasks, and the results for one class of tasks cannot be automatically transferred to all cryptographic systems based on them. In addition, the paper lacks an estimate of computational resources, such as the number of logical qubits and error correction operations necessary to implement the algorithm at cryptographically significant sizes. The expert community treats the statement with caution, given the precedents, such as the refuted paper by Yilei Chen in 2024 on a polynomial quantum algorithm for LWE, in which an error was found in a key part of the proof.