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.

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

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

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

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