Parallel lattice basis reduction - The road to many-core

Werner Backes, Susanne Wetzel

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

2 Scopus citations

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.

Original languageEnglish
Title of host publicationProc.- 2011 IEEE International Conference on HPCC 2011 - 2011 IEEE International Workshop on FTDCS 2011 - Workshops of the 2011 Int. Conf. on UIC 2011- Workshops of the 2011 Int. Conf. ATC 2011
Pages417-424
Number of pages8
DOIs
StatePublished - 2011
Event13th IEEE International Workshop on FTDCS 2011, the 8th International Conference on ATC 2011, the 8th International Conference on UIC 2011 and the 13th IEEE International Conference on HPCC 2011 - Banff, AB, Canada
Duration: 2 Sep 20114 Sep 2011

Publication series

NameProc.- 2011 IEEE International Conference on HPCC 2011 - 2011 IEEE International Workshop on FTDCS 2011 -Workshops of the 2011 Int. Conf. on UIC 2011- Workshops of the 2011 Int. Conf. ATC 2011

Conference

Conference13th IEEE International Workshop on FTDCS 2011, the 8th International Conference on ATC 2011, the 8th International Conference on UIC 2011 and the 13th IEEE International Conference on HPCC 2011
Country/TerritoryCanada
CityBanff, AB
Period2/09/114/09/11

Keywords

  • cryptanalysis
  • lattice basis reduction
  • many-core
  • parallel algorithms

Fingerprint

Dive into the research topics of 'Parallel lattice basis reduction - The road to many-core'. Together they form a unique fingerprint.

Cite this