Title :
Lock-Free GaussSieve for Linear Speedups in Parallel High Performance SVP Calculation
Author :
Mariano, Artur ; Timnat, Shahar ; Bischof, Christian
Author_Institution :
Inst. for Sci. Comput., Tech. Univ. Darmstadt, Darmstadt, Germany
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.
Keywords :
microprocessor chips; optimisation; parallel algorithms; quantum computing; quantum cryptography; vectors; GaussSieve algorithm; GaussSieve implementation; SVP-solvers; algorithmic optimization; lattice-based cryptography; lattice-based cryptosystems; linear speedup; lock-free GaussSieve; multicore CPU-chip; parallel high performance SVP calculation; parallel shared-memory implementation; quantum computer; quantum immune; sequential performance; shortest vector problem; Cryptography; Kernel; Lattices; Libraries; Optimization; Scalability; Vectors; GaussSieve; SVP; lock-free; mul1ti-core CPU; parallel;
Conference_Titel :
Computer Architecture and High Performance Computing (SBAC-PAD), 2014 IEEE 26th International Symposium on
Conference_Location :
Jussieu
DOI :
10.1109/SBAC-PAD.2014.18