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