A Quasi-polynomial Time Algorithm for the Extrapolated Dihedral Coset Problem

par Hansraj Jangir

jeudi 8 oct. 2026, 14:00 → 19:00 Europe/Paris

The Learning with Errors (LWE) problem is one of the fundamental problems in lattice-based cryptography and is believed to be hard even for quantum computers. In this talk, I will present a quantum algorithm for the Extrapolated Dihedral Coset Problem (EDCP), a quantum problem closely related to LWE. We give an algorithm for EDCP over power-of-two moduli that runs in quasi-polynomial time using a quasi-polynomial number of samples. For certain parameter regimes, this provides the fastest known algorithm for solving EDCP. The talk is largely based on joint work with Shi Bai, Elena Kirshanova, Tran Ngo, and William Youmans.