Cryptography and Lattices -- Proceedings of CALC '01
(March 29--30, 2001, Providence, Rhode Island, USA),
J. Silverman (Ed.),
vol. 2146 of
Lecture Notes in Computer Science,
Springer-Verlag.
Abstract:
Lattices are regular arrangements of points
in n-dimensional space, whose study appeared in the 19th century
in both number theory and crystallography.
Since the appearance of the celebrated Lenstra-Lenstra-Lovasz
lattice basis reduction algorithm twenty years ago, lattices have had
surprising applications in cryptology.
Until recently, the applications of lattices to cryptology
were only negative, as lattices were used to break
various 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.
We survey the main examples of the two faces of lattices in cryptology.