Cryptography 8: Foundations of Lattice Cryptography and the LLL Algorithm
This post, Part 8 of the Cryptography series, dives into the foundations of lattice-based cryptography. We begin by defining lattices, their bases, and crucial invariant properties like the determinant and successive minima. The post also analyzes the core NP-Hard computational problems on lattices, including the Shortest Vector Problem (SVP) and the Closest Vector Problem (CVP). Finally, we explore the LLL (Lenstra–Lenstra–Lovász) algorithm, a foundational basis reduction algorithm that finds approximate solutions to these problems in polynomial time.
[Read More]