On the concrete hardness of Learning with Errors

摘要: 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 LWE. In particular, we discuss algorithms proposed in the literature give expected resources required to run them. We consider both generic LWE as well small secret variants. Since several methods solving require lattice reduction step, also review use refined model estimating their running times. estimates various families instances, provide Sage module computing these highlight gaps knowledge about problem.