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
-
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},
url = {https://eprint.iacr.org/2014/775}
}
