Simon Claims Breakthrough in Quantum Algorithm for Lattice Cryptography
Daniel R. Simon, a researcher in the Amazon Web Services Cryptography Group, has claimed a significant advancement in quantum computing with a polynomial-time algorithm for the Dihedral Coset Problem (DCP). This development is consequential for post-quantum cryptography, as the DCP is connected to approximate lattice problems and Learning With Errors (LWE). Simon's algorithm, if verified, could challenge the security assumptions of lattice-based cryptography, which underpins many post-quantum cryptographic systems. The claim has not yet been peer-reviewed, and several proofs in the paper are presented as sketches. The implications of this claim are significant, as it suggests that quantum computers could efficiently solve lattice problems, which were previously considered secure against quantum attacks.