August 2019 | Martin R. Albrecht, Rachel Player, and Sam Scott
This paper presents a survey of the hardness of the Learning with Errors (LWE) problem, focusing on concrete instances and the algorithms used to solve them. The authors summarize existing algorithms for solving LWE, including strategies such as lattice reduction, BKZ, and variants of the BKW algorithm. They also discuss the computational complexity of these algorithms, including the running time of lattice reduction techniques like LLL and BKZ. The paper highlights the importance of concrete estimates for the hardness of LWE, as asymptotic analyses often fail to capture the actual computational cost. The authors provide a Sage module for estimating the running time of these algorithms and note that the LWE estimator, which accompanies this work, has not been updated since its publication. They also mention recent developments in the field, including new variants of the BKW algorithm and the dual attack, and note that some of these have not been incorporated into the LWE estimator. The paper concludes by emphasizing the need for further research to improve the understanding of the concrete hardness of LWE.This paper presents a survey of the hardness of the Learning with Errors (LWE) problem, focusing on concrete instances and the algorithms used to solve them. The authors summarize existing algorithms for solving LWE, including strategies such as lattice reduction, BKZ, and variants of the BKW algorithm. They also discuss the computational complexity of these algorithms, including the running time of lattice reduction techniques like LLL and BKZ. The paper highlights the importance of concrete estimates for the hardness of LWE, as asymptotic analyses often fail to capture the actual computational cost. The authors provide a Sage module for estimating the running time of these algorithms and note that the LWE estimator, which accompanies this work, has not been updated since its publication. They also mention recent developments in the field, including new variants of the BKW algorithm and the dual attack, and note that some of these have not been incorporated into the LWE estimator. The paper concludes by emphasizing the need for further research to improve the understanding of the concrete hardness of LWE.