Lattice Attacks on NTRU and LWE: A History of Refinements
Joppe W. Bos, Martijn Stam
Abstract
In Chapter 2, Lattice Attacks on NTRU and LWE: a History of Refinements, Martin R. Albrecht and Léo Ducas provide an overview of the advances and techniques used in the field of lattice reduction algorithms. Four decades after its invention, the LLL algorithm still plays a significant role in cryptography, not least as it has become one of the main tools to assess the security of a new wave of lattice-based cryptosystems intended for the new post-quantum cryptographic standard. The runtime of the LLL algorithm was always well understood, but the quality of its output, i.e., how short its output vectors were, could be hard to predict, even heuristically. Yet, an important aspect in the evaluation of the new lattice schemes is accurate predictions of the hardness of the underlying lattice problems, which crucially relies on estimating the 'shortness' of the vectors that can be efficiently found using lattice reduction and enumeration. Albrecht and Ducas have been on the forefront of improving such estimators and build upon their expertise in Chapter 2.