Cryptology ePrint Archive: Report 2015/046

On the concrete hardness of Learning with Errors

Martin R. Albrecht and Rachel Player and Sam Scott

Abstract: The Learning with Errors (LWE) problem has become a central building block of modern cryptographic constructions. This work collects and presents hardness results for concrete instances of LWE. In particular, we discuss algorithms proposed in the literature and give the expected resources required to run them. We consider both generic instances of LWE as well as small secret variants. Since for several methods of solving LWE we require a lattice reduction step, we also review lattice reduction algorithms and use a refined model for estimating their running times. We also give concrete estimates for various families of LWE instances, provide a Sage module for computing these estimates and highlight gaps in the knowledge about algorithms for solving the Learning with Errors problem.

Category / Keywords: foundations / Learning with Errors, Lattice-based Cryptography, Lattice Reduction

Original Publication (in the same form): Journal of Mathematical Cryptology

Date: received 19 Jan 2015, last revised 25 Sep 2015

Contact author: rachel player 2013 at live rhul ac uk

Available format(s): PDF | BibTeX Citation

Version: 20150925:162934 (All versions of this report)

Short URL: ia.cr/2015/046

Discussion forum: Show discussion | Start new discussion