Abstract:
Lattices are regular arrangements of points
in space, whose study appeared in the 19th century
in both number theory and crystallography.
The goal of lattice reduction is to find
useful representations of lattices.
A major breakthrough in that field occurred twenty years ago,
with the appearance of Lovasz's reduction algorithm, also known as LLL or L^3.
Lattice reduction algorithms have since proved
invaluable in many areas of mathematics and computer science,
especially in algorithmic number theory and cryptology.
In this paper, we survey some applications of lattices to cryptology.
We focus on recent developments of lattice reduction
both in cryptography and cryptanalysis,
which followed seminal works of
Ajtai and Coppersmith.