Cryptology ePrint Archive: Report 2016/890

A Parallel Variant of LDSieve for the SVP on Lattices

Artur Mariano and 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.

Category / Keywords: foundations / lattices, sieving algorithms, parallel algorithms, shortest vector problem (SVP)

Original Publication (with minor differences): PDP 2017
DOI: 10.1109/PDP.2017.60

Date: received 12 Sep 2016, last revised 23 Feb 2018

Contact author: mail at thijs com

Available format(s): PDF | BibTeX Citation

Version: 20180223:141855 (All versions of this report)

Short URL: ia.cr/2016/890

Discussion forum: Show discussion | Start new discussion