Cryptanalysis and Security Estimates

Security estimates and parameter choice for lattice based cryptography are described in

  1. Lattice-Based Cryptography (Micciancio & Regev, Post Quantum Cryptography, 2009)

  2. Better Key Sizes (and Attacks) for LWE-Based Encryption (Lindner & Peikert, CT-RSA 2011)

  3. On the concrete hardness of Learning with Errors (Albrecht, Payer & Scott, ePrint 2015)

For recent work on the experimental evaluation of lattice reduction algorithms used in cryptanalysis see

  1. BKZ 2.0: Better Lattice Security Estimates (Chen & Nguyen, Asiacrypt 2011)

  2. Solving BDD by Enumeration: An Update (Liu & Nguyen, CT-RSA 2013)


Test challenges for various lattice problems of interest in cryptography are given in the following pages:

Combinatorial Attacks

  1. Lazy Modulus Switching for the BKW Algorithm on LWE (Albrecht, Faugere, Fitzpatrick & Perret, PKC 2014)

  2. On the Complexity of the BKW Algorithm against LWE (Albrecht, Cid, Faugere, Fitzpatrick & Perret, DCC 2015)

  3. On the Efficacy of Solving LWE by Reduction to Unique-SVP (Albrecht, Fitzpatrick & Gopfert, ICISC 2013)

  4. Better Algorithms for LWE and LWR (Duc, Tramer & Vaudenay, Eurocrypt 2015)

Algebraic Attacks

  1. New Algorithms for Learning in Presence of Errors (Arora & Ge, ICALP 2011)

  2. Algebraic Algorithms for LWE (Albrecht, Cid, Faugere & Perret, ePrint 2014)

  3. On the Complexity of the Arora-Ge Algorithm against LWE (Albrecht, Cid, Faugere, Fitzpatrick & Perret, SCC 2012)