An Improved BKW Algorithm for LWE with Applications to Cryptography and Lattices

Paul Kirchner, Pierre-Alain Fouque

In this paper, we study the Learning With Errors problem and its binary variant, where secrets and errors are binary or taken in a small interval. We introduce a new variant of the…