Overall optimization of the enumeration approach for the LWE problem

Abstract

Learning with errors (LWE) problem is an well-known problem for lattice cryptography. After Lindner and Peikert suggested an attack using bounded distance decoding (BDD) problem [LP11], it has been studied as one of the most practical ways to solve the LWE problem. We revisit the numerical optimization [GNR10] to optimize the BDD approach with pruned enumeration for solving LWE problem. Numerical minimization also takes the lattice reduction, enumeration radius, and subdimension into consideration.