A Parallel Implementation of GaussSieve for the Shortest Vector Problem in Lattices

Autor:	Michael Schneider, Benjamin Milde
Rok vydání:	2011
Předmět:	Sieving algorithms Multi-core processor Computer science Lattice problem Lattice sieving Small number Lattice-based cryptography Parallel computing Multicore cpu
Zdroj:	Lecture Notes in Computer Science ISBN: 9783642231773 PaCT
DOI:	10.1007/978-3-642-23178-0_40
Popis:	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.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::e77822b3c6bb716104e8107d9801680e https://doi.org/10.1007/978-3-642-23178-0_40 Zobrazit plný text záznamu