Abstract
In this paper, we propose a parallel implementation of LDSieve, a recently published sieving algorithm for the SVP, which achieves the best theoretical complexity to this day, on parallel shared-memory systems. In particular, we propose a scalable parallel variant of LDSieve that is probabilistically lock-free and relaxes the properties of the algorithm to favour parallelism. We use our parallel variant of LDSieve to answer a number of important questions pertaining to the algorithm. In particular, we show that LDSieve scales fairly well on shared-memory systems and uses much less memory than HashSieve on random lattices, for the same or even less execution time.
Original language | English |
---|---|
Title of host publication | 2017 25th Euromicro International Conference on Parallel, Distributed and Network-Based Processing, PDP 2017, St. Petersburg, Russia, 6-8 March 2017 : Proceedings |
Place of Publication | Piscataway |
Publisher | Institute of Electrical and Electronics Engineers |
Pages | 23-30 |
Number of pages | 8 |
ISBN (Electronic) | 978-1-5090-6058-0 |
ISBN (Print) | 978-1-5090-6059-7 |
DOIs | |
Publication status | Published - 26 Apr 2017 |
Externally published | Yes |
Event | 25th Euromicro International Conference on Parallel, Distributed and Network-Based Processing (PDP 2017) - St. Petersburg, Russian Federation Duration: 6 Mar 2017 → 8 Mar 2017 Conference number: 25 https://www.pdp2017.org |
Conference
Conference | 25th Euromicro International Conference on Parallel, Distributed and Network-Based Processing (PDP 2017) |
---|---|
Abbreviated title | PDP 2017 |
Country/Territory | Russian Federation |
City | St. Petersburg |
Period | 6/03/17 → 8/03/17 |
Internet address |
Keywords
- hashsieve
- lattices cryptography
- multi-core
- parallel