Paper 2014/714

A comprehensive empirical comparison of parallel ListSieve and GaussSieve

Artur Mariano, 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.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. APCIE14
Contact author(s)
artur mariano @ sc tu-darmstadt de
History
2014-09-16: received
Short URL
https://ia.cr/2014/714
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/714,
      author = {Artur Mariano and Ozgur Dagdelen and Christian Bischof},
      title = {A comprehensive empirical comparison of parallel ListSieve and GaussSieve},
      howpublished = {Cryptology ePrint Archive, Paper 2014/714},
      year = {2014},
      note = {\url{https://eprint.iacr.org/2014/714}},
      url = {https://eprint.iacr.org/2014/714}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.