Book contents
- Frontmatter
- Contents
- List of Contributors
- Preface
- 1 Introduction
- Part I Cryptanalysis
- 2 Lattice Attacks on NTRU and LWE: A History of Refinements
- 3 History of Integer Factorisation
- 4 Lattice-Based Integer Factorisation: An Introduction to Coppersmith’s Method
- 5 Computing Discrete Logarithms
- 6 RSA, DH and DSA in the Wild
- 7 A Survey of Chosen-Prefix Collision Attacks
- Part II Implementations
- References
- Index
2 - Lattice Attacks on NTRU and LWE: A History of Refinements
from Part I - Cryptanalysis
Published online by Cambridge University Press: 11 November 2021
- Frontmatter
- Contents
- List of Contributors
- Preface
- 1 Introduction
- Part I Cryptanalysis
- 2 Lattice Attacks on NTRU and LWE: A History of Refinements
- 3 History of Integer Factorisation
- 4 Lattice-Based Integer Factorisation: An Introduction to Coppersmith’s Method
- 5 Computing Discrete Logarithms
- 6 RSA, DH and DSA in the Wild
- 7 A Survey of Chosen-Prefix Collision Attacks
- Part II Implementations
- References
- Index
Summary
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 stillplays 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 latticeproblems, 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.
- Type
- Chapter
- Information
- Computational CryptographyAlgorithmic Aspects of Cryptology, pp. 15 - 40Publisher: Cambridge University PressPrint publication year: 2021
- 7
- Cited by