August 2019 | Martin R. Albrecht, Rachel Player, and Sam Scott
The paper "On the Concrete Hardness of Learning with Errors" by Martin R. Albrecht, Rachel Player, and Sam Scott reviews and presents hardness results for concrete instances of the Learning with Errors (LWE) problem. The authors discuss various algorithms proposed in the literature and provide expected resources required to run them. They consider both generic instances of LWE and small secret variants, focusing on lattice reduction algorithms and their running times. The paper also includes a Sage module for computing concrete estimates for different families of LWE instances and highlights gaps in the knowledge about solving the LWE problem. The authors caution that the work has not been updated since its publication, and readers should not rely on it as a reference for the state-of-the-art in assessing the cost of solving LWE. The paper is structured into several sections, covering relevant tools, lattice reduction algorithms, strategies for solving LWE, and concrete estimates for various parameter choices.The paper "On the Concrete Hardness of Learning with Errors" by Martin R. Albrecht, Rachel Player, and Sam Scott reviews and presents hardness results for concrete instances of the Learning with Errors (LWE) problem. The authors discuss various algorithms proposed in the literature and provide expected resources required to run them. They consider both generic instances of LWE and small secret variants, focusing on lattice reduction algorithms and their running times. The paper also includes a Sage module for computing concrete estimates for different families of LWE instances and highlights gaps in the knowledge about solving the LWE problem. The authors caution that the work has not been updated since its publication, and readers should not rely on it as a reference for the state-of-the-art in assessing the cost of solving LWE. The paper is structured into several sections, covering relevant tools, lattice reduction algorithms, strategies for solving LWE, and concrete estimates for various parameter choices.