Paper 2016/890

A Parallel Variant of LDSieve for the SVP on Lattices

Artur Mariano, Thijs Laarhoven, and Christian Bischof

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 sharedmemory systems and uses much less memory than HashSieve on random lattices, for the same or even less execution time.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Minor revision. PDP 2017
DOI
10.1109/PDP.2017.60
Keywords
latticessieving algorithmsparallel algorithmsshortest vector problem (SVP)
Contact author(s)
mail @ thijs com
History
2018-02-23: revised
2016-09-14: received
See all versions
Short URL
https://ia.cr/2016/890
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/890,
      author = {Artur Mariano and Thijs Laarhoven and Christian Bischof},
      title = {A Parallel Variant of LDSieve for the SVP on Lattices},
      howpublished = {Cryptology ePrint Archive, Paper 2016/890},
      year = {2016},
      doi = {10.1109/PDP.2017.60},
      note = {\url{https://eprint.iacr.org/2016/890}},
      url = {https://eprint.iacr.org/2016/890}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.