The course lastw 4 weeks starting May 30 (Wednesday) up to June 20 (Wednesday)
Lattices are regular arrangements of points in the n-dimensional space, whose study appeared in the 19th century in both number theory and crystallography. From an algorithmic point of view, one is interested in finding useful representations of lattices.
A major breakthrough in that field occured twenty years ago, with the appearance of Lovasz's lattice basis 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. Until recently, the applications of lattices to cryptology were only negative, as lattices were used to break many cryptographic schemes. Paradoxically, several positive cryptographic applications of lattices have emerged in the past five years: there now exist public-key cryptosystems based on the hardness of lattice problems, and lattices play a crucial role in a few security proofs including the one of the widely used RSA encryption standard called RSA-OAEP.
The goal of this course is two-fold. We will try to give an introduction to lattice theory, both from a mathematical and an algorithmic point of view. Then we will present the main applications of lattices to cryptology, both in cryptography and cryptanalysis.
Return zur Homepage http://www.mi.informatik.uni-frankfurt.de.
Last modified: May 09, 2001