On the concrete hardness of Learning with Errors

26.03.2015, 15:00 – 16:00

2015/03/26 15:00-16:00

Speaker: Rachel Player | Location: Mornewegstraße 32 (S4|14), Room 3.1.01, Darmstadt

Organizer: Giorgia Azzurra Marson / Nina Bindel


The Learning with Errors (LWE) problem has become a central building block of modern cryptographic constructions. We will discuss 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 propose 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.

Short Bio

Rachel Player is studying for a PhD in Information Security at Royal Holloway, University of London under the supervision of Professor Carlos Cid and Professor Sean Murphy. Previously she studied Mathematics at Warwick, graduating with the MMath (Hons., First Class) in July 2013. Her research interests are lattice-based cryptography and the Learning with Errors problem.