Paper Info
Title
A parallel implementation of GaussSieve for the shortest vector problem in lattices
Abstract
The security of lattice based cryptography can be considered to be based on the hardness of the shortest vector problem (SVP) in lattices. Sieving algorithms can be used to solve this problem, at least in small dimensions. The most promising among the sieving algorithms is GaussSieve. In this paper we present a parallel version of the GaussSieve algorithm that solves the shortest vector problem in lattices. For small number of up to 5 parallel threads, the parallel version scales nearly linearly. For bigger numbers of threads, the efficiency decreases. We implement the parallel GaussSieve on multicore CPUs, whereas the presented ideas can also be implemented on different parallel platforms.
Year
DOI
Venue
2011
10.1007/978-3-642-23178-0_40
PACT
Keywords
Field
DocType
parallel version scale,parallel implementation,shortest vector problem,different parallel platform,parallel gausssieve,parallel thread,small dimension,sieving algorithm,small number,parallel version,gausssieve algorithm
Small number,Lattice (order),Computer science,Parallel computing,Multicore cpu,Lattice problem,Thread (computing),Lattice-based cryptography,Sieving algorithms,Multi-core processor
Conference
Volume
ISSN
Citations 
6873
0302-9743
17
PageRank 
References 
Authors
0.70
7
2
Name
Order
Citations
PageRank
Benjamin Milde1425.20
michael schneider255576.50