Complexity of Lattice Problems: A Cryptographic Perspective

Lattices are geometric objects that can be pictorially described as the set of intersection points of an infinite, regular n-dimensional grid. De­ spite their apparent simplicity, lattices hide a rich combinatorial structure, which has attracted the attention of great mathematicians over the last two centuries. Not surprisingly, lattices have found numerous applications in mathematics and computer science, ranging from number theory and Diophantine approximation, to combinatorial optimizati...