A parallel variant of LDSieve for the SVP on lattices

Artur Mariano, Thijs Laarhoven, Christian Bischof

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

9 Citations (Scopus)

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 languageEnglish
Title of host publication2017 25th Euromicro International Conference on Parallel, Distributed and Network-Based Processing, PDP 2017, St. Petersburg, Russia, 6-8 March 2017 : Proceedings
Place of PublicationPiscataway
PublisherInstitute of Electrical and Electronics Engineers
Pages23-30
Number of pages8
ISBN (Electronic)978-1-5090-6058-0
ISBN (Print)978-1-5090-6059-7
DOIs
Publication statusPublished - 26 Apr 2017
Externally publishedYes
Event25th Euromicro International Conference on Parallel, Distributed and Network-Based Processing (PDP 2017) - St. Petersburg, Russian Federation
Duration: 6 Mar 20178 Mar 2017
Conference number: 25
https://www.pdp2017.org

Conference

Conference25th Euromicro International Conference on Parallel, Distributed and Network-Based Processing (PDP 2017)
Abbreviated titlePDP 2017
CountryRussian Federation
CitySt. Petersburg
Period6/03/178/03/17
Internet address

Keywords

  • hashsieve
  • lattices cryptography
  • multi-core
  • parallel

Fingerprint Dive into the research topics of 'A parallel variant of LDSieve for the SVP on lattices'. Together they form a unique fingerprint.

Cite this