Cryptology ePrint Archive: Report 2012/533

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

Thijs Laarhoven and 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.

Category / Keywords: foundations / lattices, hard lattice problems, lattice basis reduction, shortest vector problem, lattice-based cryptosystems

Date: received 10 Sep 2012

Contact author: t m m laarhoven at tue nl

Available formats: PDF | BibTeX Citation

Version: 20120920:070804 (All versions of this report)

Discussion forum: Show discussion | Start new discussion