SIS/LWE Cryptanalysis

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 addresses 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] is updated with recent developments, and includes an on-line security estimator.

  1. On the concrete hardness of Learning with Errors
    (Albrecht,Player,Scott - J. Math Crypto) [code]

There are three general classes of attacks to LWE, based on primal lattice, dual lattice, and combinatorial techniques.

Primal Lattice Attack

Primal lattice attacks to LWE results in an instance of the Bounded Distance Decoding or Unique Shortest Vector Problem.

  1. Revisiting the Expected Cost of Solving uSVP and Applications to LWE
    (Albrecht, Gopfert, Virdia, Wunderer - AsiaCrypt 2017) [video][code]

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

Dual Lattice Attacks

The dual attack reduces the decisional LWE problem to the SIS problem in the dual lattice.

  1. On dual lattice attacks against small-secret LWE and parameter choices in HElib and SEAL
    (Albrecht - EuroCrypt 2017) [video]

Combinatorial Attacks

  1. Coded-BKW with Sieving
    (Guo, Johansson, Martensson, Stankovski - AsiaCrypt 2017) [video]

  2. Coded-BKW: Solving LWE Using Lattice Codes
    (Guo, Johansson, Martensson, Stankovski - Crypto 2017)

  3. On the complexity of the BKW algorithm on LWE
    (Albrecht, Cid, Faugere, Fitzpatrick, Perret - Des. Codes Crypto 2015)

  4. Lazy Modulus Switching for the BKW Algorithm on LWE
    (Albrecht, Faugere, Fitzpatric, Perret - PKC 2014)

  5. Algebraic Algorithms for LWE Problems
    (Albrecht, Cid. Faugere, Fitzpatrick, Perret - ACM Comm Comp Algebra 2015)