Date de l'exposé : 20 janvier 2023
Dual attacks on LWE
In this talk, I will present some recent work on Learning With Errors (LWE), a very important problem for the security of post-quantum cryptography. Specifically, I focus on so-called dual attacks. First, I will explain how those attacks work and why they fundamentally reduce to a problem about the Discrete Fourier Transform (DFT). Then, I will explain how we obtain a quantum speed-up of those attacks by leveraging tools such as quantum amplitude estimation. Finally, I will explain how we can obtain classical speed-ups by using ideas from coding theory applied to lattices.