Parallel Shortest Lattice Vector Enumeration on Graphics Cards

In this paper the authors 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. They gain large speedups compared to previous serial CPU implementations. The 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. The work results in an advance in practical lattice reduction.

Provided by: Katholieke Universiteit Leuven Topic: Hardware Date Added: Feb 2010 Format: PDF

Download Now

Find By Topic