Worst-case to average-case reductions for lattice problems provide a solid theoretical foundation for the use of the SIS and LWE problems in the construction of cryptographic applications, but offer very little guidance on choosing appropriate key sizes and parameters required to meet specific levels of security. In practice, the concrete security of lattice cryptography is estimated directly by evaluating the cost of solving random instances of SIS and LWE. In this context, cryptanalysis of lattice problems refers to estimating the average cost of solving random SIS and LWE instances.
This page collects references that directly address the average-case complexity of SIS and LWE, often using specialized algorithms that are not applicable to arbitrary (worst-case) lattice problems.
Methods to attacks LWE and evaluate its concrete security are surveyed in (1). The code page provides both an on-line estimator and a sage script for local execution, which are updated to include more recent developments. The estimator is used in (2) to evaluate the security of a wide range of lattice-based encryption and digital signature schemes proposed to the NIST Post-Quantum Cryptography standardization process. See also the Homomorphic Encryption Standardization page for LWE security estimates and parameter recommendations.
On the concrete hardness of Learning with Errors
Albrecht, Player, Scott - J. Math. Crypto. 2015 [ePrint] [code]
Estimate All the {LWE, NTRU} Schemes!
Albrecht, Curtis, Deo, Davidson, Player, Postlethwaite, Virdia & Wunderer - SCN 2018. [ePrint]
There are three general classes of attacks to LWE, based on primal lattice, dual lattice, and combinatorial techniques.
Primal lattice attacks to LWE results in an instance of the Bounded Distance Decoding or Unique Shortest Vector Problem.
Revisiting the Expected Cost of Solving uSVP and Applications to LWE
Albrecht, Gopfert, Virdia, Wunderer - AsiaCrypt 2017. [ePrint] [video] [code]
On the Efficacy of Solving LWE by Reduction to Unique-SVP
Albrecht, Fitzpatrick, Gopfer - ICISC 2013. [ePrint]
The dual attack reduces the decisional LWE problem to the SIS problem in the dual lattice. These attacks are also relevant to estimate the security of SIS.
The Asymptotic Complexity of Coded-BKW with Sieving Using Increasing Reduction Factors
(Martensson - ISIT 2019)
Coded-BKW with Sieving
(Guo, Johansson, Martensson, Stankovski - AsiaCrypt 2017) [video]
Coded-BKW: Solving LWE Using Lattice Codes
(Guo, Johansson, Stankovski - Crypto 2015)
On the complexity of the BKW algorithm on LWE
(Albrecht, Cid, Faugere, Fitzpatrick, Perret - Des. Codes Crypto 2015)
Lazy Modulus Switching for the BKW Algorithm on LWE
(Albrecht, Faugere, Fitzpatric, Perret - PKC 2014)
Algebraic Algorithms for LWE Problems
(Albrecht, Cid, Faugere, Fitzpatrick, Perret - ACM Comm Comp Algebra 2015)
The General Sieve Kernel and New Records in Lattice Reduction
(Albrecht, Ducas, Herold, Kirshanova, Postlethwaite, Stevens - ePrint 2019)
Improved Combinatorial Algorithms for the Inhomogeneous Short Integer Solution Problem
Bai, Galbraith, Li, Sheffield - J. Crypto 2019. [ePrint]
Lattice Decoding Attacks on Binary LWE
(Bai, Galbraith - ACISP 2014)
Post-quantum Key Exchange - A New Hope
(Alkim, Ducas, Poppelmann, Schwabe - USENIX 2016)