TU Darmstadt / ULB / TUbiblio

A Parallel Variant of LDSieve for the SVP on Lattices

Mariano, Artur and Laarhoven, Thijs and Bischof, Christian (2017):
A Parallel Variant of LDSieve for the SVP on Lattices.
In: 2017 25th Euromicro International Conference on Parallel, Distributed and Network-based Processing (PDP), IEEE, In: 2017 25th Euromicro International Conference on Parallel, Distributed and Network-based Processing (PDP), DOI: 10.1109/PDP.2017.60,
[Online-Edition: https://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber...],
[Conference or Workshop Item]

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.

Item Type: Conference or Workshop Item
Erschienen: 2017
Creators: Mariano, Artur and Laarhoven, Thijs and Bischof, Christian
Title: A Parallel Variant of LDSieve for the SVP on Lattices
Language: English
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.

Title of Book: 2017 25th Euromicro International Conference on Parallel, Distributed and Network-based Processing (PDP)
Publisher: IEEE
Uncontrolled Keywords: Primitives; P1
Divisions: 20 Department of Computer Science
20 Department of Computer Science > Scientific Computing
DFG-Collaborative Research Centres (incl. Transregio)
DFG-Collaborative Research Centres (incl. Transregio) > Collaborative Research Centres
Profile Areas
Profile Areas > Cybersecurity (CYSEC)
DFG-Collaborative Research Centres (incl. Transregio) > Collaborative Research Centres > CRC 1119: CROSSING – Cryptography-Based Security Solutions: Enabling Trust in New and Next Generation Computing Environments
Event Title: 2017 25th Euromicro International Conference on Parallel, Distributed and Network-based Processing (PDP)
Date Deposited: 06 Sep 2018 13:29
DOI: 10.1109/PDP.2017.60
Official URL: https://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber...
Export:
Suche nach Titel in: TUfind oder in Google

Optionen (nur für Redakteure)

View Item View Item