AWS researcher Daniel Simon introduces a quantum algorithm that may accelerate solutions to mathematical problems in post-quantum cryptography.
Daniel Simon, a researcher at Amazon Web Services (AWS), has unveiled a novel quantum algorithm that could significantly enhance the speed of solving certain mathematical problems related to post-quantum cryptography.
Simon asserts that the algorithm's runtime increases polynomially with the complexity of the task, contrasting with the exponential growth seen in traditional computing methods. This breakthrough could alter our perceptions of the security of certain cryptographic problems against quantum computing threats. However, the research does not propose a direct attack on established standards like ML-KEM and ML-DSA.
Simon is known for his earlier work in the 1990s, which introduced a quantum algorithm that illustrated quantum computation's advantages, paving the way for Shor's algorithm. In his latest research, he focuses on the Dihedral Coset Problem (DCP), where a quantum computer must discern a hidden value from a set of entangled states.
Although DCP is not directly used to secure crypto wallets or online communications, it is significant due to its connections with problems foundational to lattice-based cryptography. In the early 2000s, Oded Regev showed that an efficient algorithm for DCP could address certain variants of high-dimensional lattice problems, but previous polynomial approaches required idealized tools for complex computational tasks.
Simon claims to have addressed this limitation, stating that his algorithm can execute the necessary transformations directly on a quantum computer.
Potential Impact on Cryptography Standards
When integrated with existing mathematical research, Simon's algorithm may also apply to variations of the Shortest Vector Problem (SVP) and Learning With Errors (LWE). SVP involves finding shorter paths within complex multidimensional structures, while LWE conceals secrets within distorted systems of equations.
Current classical computers have difficulty solving large instances of these problems efficiently, and it is anticipated that future quantum computers will face similar challenges. This reliance on lattice-based mathematics is why post-quantum cryptography is gaining traction, particularly following the U.S. National Institute of Standards and Technology (NIST) standardization of the ML-KEM key encapsulation mechanism in 2024, which relies on the complexity of Module Learning With Errors.
Additionally, the ML-DSA digital signature standard is founded on lattice cryptography principles. If Simon's findings are validated, it would suggest that quantum computers could solve certain related problems much more efficiently than previously understood.
Current Security of ML-KEM
It is crucial to clarify that Simon's research does not imply that quantum computers can currently break the ML-KEM key or forge ML-DSA signatures. His work focuses on mathematical problems rather than direct attacks on specific cryptographic standards. Moreover, LWE encompasses a wide variety of problems, and insights from one class cannot be universally applied to all cryptographic systems based on it.
The preprint lacks an evaluation of the required logical qubits, quantum gates, or error correction needed to implement the algorithm at sizes relevant for cryptography. As of now, there is no consensus among independent experts regarding the research's validity.
Historically, the field has seen instances where initial promising findings did not hold up under scrutiny. For example, in 2024, researcher Yilei Chen withdrew a polynomial quantum algorithm for LWE after experts identified a flaw in a key aspect of the proof.
As a reminder, developers at Quantus recently underscored the vulnerability of many algorithms currently used in the crypto industry to potential quantum attacks, highlighting the urgency for a shift to post-quantum solutions.
