Paper 2014/775

Lock-free GaussSieve for Linear Speedups in Parallel High Performance SVP Calculation

Artur Mariano, Shahar Timnat, and Christian Bischof

Abstract

Lattice-based cryptography became a hot-topic in the past years because it seems to be quantum immune, i.e., resistant to attacks operated with quantum computers. The security of lattice-based cryptosystems is determined by the hardness of certain lattice problems, such as the Shortest Vector Problem (SVP). Thus, it is of prime importance to study how efficiently SVP-solvers can be implemented. This paper presents a parallel shared-memory implementation of the GaussSieve algorithm, a well known SVP-solver. Our implementation achieves almost linear and linear speedups with up to 64 cores, depending on the tested scenario, and delivers better sequential performance than any other disclosed GaussSieve implementation. In this paper, we show that it is possible to implement a highly scalable version of GaussSieve on multi-core CPU-chips. The key features of our implementation are a lock-free singly linked list, and hand-tuned, vectorized code. Additionally, we propose an algorithmic optimization that leads to faster convergence.

Note: Final (full) version of the paper.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. MINOR revision.SBAC-PAD'14 - 26th International Symposium on Computer Architecture and High Performance Computing
Contact author(s)
artur mariano @ sc tu-darmstadt de
History
2014-10-01: received
Short URL
https://ia.cr/2014/775
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/775,
      author = {Artur Mariano and Shahar Timnat and Christian Bischof},
      title = {Lock-free GaussSieve for Linear Speedups in Parallel High Performance SVP Calculation},
      howpublished = {Cryptology ePrint Archive, Paper 2014/775},
      year = {2014},
      note = {\url{https://eprint.iacr.org/2014/775}},
      url = {https://eprint.iacr.org/2014/775}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.