LLL Algorithm

In this 9th installment of the Cryptography series, we explore the powerful applications of lattice reduction in both algebra and cryptanalysis. Specifically, we demonstrate how modeling problems as finding short vectors in a lattice allows us to efficiently solve the Minimal Polynomial reconstruction, Coppersmith’s method for finding small roots, Low-density Subset Sum problems (Knapsack), and the Hidden Number Problem (HNP). [Read More]

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]