Cryptology ePrint Archive: Report 2009/601
Parallel Shortest Lattice Vector Enumeration on Graphics Cards
Jens Hermans and Michael Schneider and Johannes Buchmann and 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.
Category / Keywords: implementation / Lattice reduction, enumeration, parallelization, graphics cards
Date: received 4 Dec 2009, last revised 26 Feb 2010
Contact author: mischnei at cdc informatik tu-darmstadt de
Available format(s): PDF | BibTeX Citation
Version: 20100226:162624 (All versions of this report)
Short URL: ia.cr/2009/601
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]