Paper 2014/775

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

Artur Mariano, Shahar Timnat, and Christian Bischof


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.

Available format(s)
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
2014-10-01: received
Short URL
Creative Commons Attribution


      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{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.