articleJournal of Mathematical CryptologyOct 1, 2015HYBRID OA

On the concrete hardness of Learning with Errors

MAM. AlbrechtRPRachel PlayerSSSam Scott

Royal Holloway University of London

Indexed incrossrefdoaj

Abstract

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…

Citation impact

783
total citations
FWCI
56.54
Percentile
100%
References
0
Citations per year

Authors

3

Topics & keywords

Topics
Keywords
  • Learning with errors
  • Cryptography
  • Computer science
  • Reduction (mathematics)
  • Theoretical computer science
  • Lattice (music)
  • Block (permutation group theory)
  • Lattice reduction
UN Sustainable Development Goals
  • Sustainable cities and communities
No related works found for this paper.

Funding