AWS Researcher Proposes Quantum Algorithm That Could Challenge Post-Quantum Cryptography Foundations

An Amazon Web Services cryptographer has proposed a polynomial-time quantum algorithm for the Dihedral Coset Problem, a significant theoretical advance in quantum algorithms. The problem is connected to lattice mathematics and could have implications for post-quantum cryptography.

The new algorithm removes a key limitation in previous approaches and claims tolerance for certain faulty quantum samples. It presents a method for obtaining a square-root-of-n times polylogarithmic approximation to the shortest vector in an n-dimensional lattice, which is essential for many post-quantum encryption systems.

The research does not demonstrate a practical attack on standardized post-quantum cryptography and estimates that the quantum hardware required would still be too powerful to exist currently. The algorithm's tolerance for faulty samples could have significant implications for lattice-based cryptography.