Paper 2009/601

Parallel Shortest Lattice Vector Enumeration on Graphics Cards

Jens Hermans, Michael Schneider, Johannes Buchmann, Frederik Vercauteren, and Bart Preneel

Abstract

In this paper we present an algorithm for parallel exhaustive search for short vectors in lattices. This algorithm can be applied to a wide range of parallel computing systems. To illustrate the algorithm, it was implemented on graphics cards using CUDA, a programming framework for NVIDIA graphics cards. We gain large speedups compared to previous serial CPU implementations. Our implementation is almost 5 times faster in high lattice dimensions. Exhaustive search is one of the main building blocks for lattice basis reduction in cryptanalysis. Our work results in an advance in practical lattice reduction.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Published elsewhere. Unknown where it was published
Keywords
Lattice reductionenumerationparallelizationgraphics cards
Contact author(s)
mischnei @ cdc informatik tu-darmstadt de
History
2010-02-26: last of 2 revisions
2009-12-09: received
See all versions
Short URL
https://ia.cr/2009/601
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2009/601,
      author = {Jens Hermans and Michael Schneider and Johannes Buchmann and Frederik Vercauteren and Bart Preneel},
      title = {Parallel Shortest Lattice Vector Enumeration on Graphics Cards},
      howpublished = {Cryptology ePrint Archive, Paper 2009/601},
      year = {2009},
      note = {\url{https://eprint.iacr.org/2009/601}},
      url = {https://eprint.iacr.org/2009/601}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.