Title :
Parallel Lattice Basis Reduction - The Road to Many-Core
Author :
Backes, Werner ; Wetzel, Susanne
Author_Institution :
Dept. of Comput. Sci., Stevens Inst. of Technol., Hoboken, NJ, USA
Abstract :
This paper introduces a new parallel algorithm that allows for an efficient LLL reduction using today´s emerging many-core systems. This work develops suitable methods that efficiently implement the idea of splitting a lattice basis into smaller sub problems, LLL reducing the sub problems, and recombining the sub problems afterwards to obtain an overall LLL reduced basis. The new many-core algorithm outperforms any current parallel LLL algorithm. Experiments on a 48-core test system show a speed-up of approximately 10 for SVP challenge type lattice bases and a remarkable speed-up of approximately 50 for knapsack type lattice bases.
Keywords :
multiprocessing systems; parallel algorithms; LLL reduction; many-core systems; parallel algorithm; parallel lattice basis reduction; Algorithm design and analysis; Approximation algorithms; Cryptography; Lattices; Runtime; Servers; Vectors; cryptanalysis; lattice basis reduction; many-core; parallel algorithms;
Conference_Titel :
High Performance Computing and Communications (HPCC), 2011 IEEE 13th International Conference on
Conference_Location :
Banff, AB
Print_ISBN :
978-1-4577-1564-8
Electronic_ISBN :
978-0-7695-4538-7
DOI :
10.1109/HPCC.2011.61
