Cryptology ePrint Archive: Report 2014/714

A comprehensive empirical comparison of parallel ListSieve and GaussSieve

Artur Mariano and Ozgur Dagdelen and Christian Bischof

Abstract: The security of lattice-based cryptosystems is determined by the performance of practical implementations of, among others, algo- rithms for the Shortest Vector Problem (SVP). In this paper, we conduct a comprehensive, empirical comparison of two SVP-solvers: ListSieve and GaussSieve. We also propose a practical par- allel implementation of ListSieve, which achieves super-linear speedups on multi-core CPUs, with efficiency levels as high as 183%. By compar- ing our implementation with a parallel implementation of GaussSieve, we show that ListSieve can, in fact, outperform GaussSieve for a large num- ber of threads, thus answering a question that was still open to this day.

Category / Keywords:

Original Publication (in the same form): APCIE14

Date: received 12 Sep 2014

Contact author: artur mariano at sc tu-darmstadt de

Available format(s): PDF | BibTeX Citation

Version: 20140916:160834 (All versions of this report)

Short URL: ia.cr/2014/714

Discussion forum: Show discussion | Start new discussion