Paper 2012/533

Solving Hard Lattice Problems and the Security of Lattice-Based Cryptosystems

Thijs Laarhoven, Joop van de Pol, and Benne de Weger

Abstract

This paper is a tutorial introduction to the present state-of-the-art in the field of security of lattice-based cryptosystems. After a short introduction to lattices, we describe the main hard problems in lattice theory that cryptosystems base their security on, and we present the main methods of attacking these hard problems, based on lattice basis reduction. We show how to find shortest vectors in lattices, which can be used to improve basis reduction algorithms. Finally we give a framework for assessing the security of cryptosystems based on these hard problems.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Unknown where it was published
Keywords
latticeshard lattice problemslattice basis reductionshortest vector problemlattice-based cryptosystems
Contact author(s)
t m m laarhoven @ tue nl
History
2012-09-20: received
Short URL
https://ia.cr/2012/533
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2012/533,
      author = {Thijs Laarhoven and Joop van de Pol and Benne de Weger},
      title = {Solving Hard Lattice Problems and the Security of Lattice-Based Cryptosystems},
      howpublished = {Cryptology ePrint Archive, Paper 2012/533},
      year = {2012},
      note = {\url{https://eprint.iacr.org/2012/533}},
      url = {https://eprint.iacr.org/2012/533}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.