A parallel variant of LDSieve for the SVP on lattices

Artur Mariano; Thijs Laarhoven; Christian Bischof

doi:10.1109/PDP.2017.60

A parallel variant of LDSieve for the SVP on lattices

Artur Mariano, Thijs Laarhoven, Christian Bischof

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-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 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	https://doi.org/10.1109/PDP.2017.60
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	Russian Federation
City	St. Petersburg
Period	6/03/17 → 8/03/17
Internet address	https://www.pdp2017.org

Keywords

hashsieve
lattices cryptography
multi-core
parallel

Access to Document

10.1109/PDP.2017.60

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

Mariano, A., Laarhoven, T., & Bischof, C. (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 2017, St. Petersburg, Russia, 6-8 March 2017 : Proceedings (pp. 23-30). [7912621] Institute of Electrical and Electronics Engineers. https://doi.org/10.1109/PDP.2017.60

@inproceedings{ac92f4ee3476470695643bb6b1d6feef,

title = "A parallel variant of LDSieve for the SVP on lattices",

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.",

keywords = "hashsieve, lattices cryptography, multi-core, parallel",

author = "Artur Mariano and Thijs Laarhoven and Christian Bischof",

year = "2017",

month = apr,

day = "26",

doi = "10.1109/PDP.2017.60",

language = "English",

isbn = "978-1-5090-6059-7 ",

pages = "23--30",

booktitle = "2017 25th Euromicro International Conference on Parallel, Distributed and Network-Based Processing, PDP 2017, St. Petersburg, Russia, 6-8 March 2017 : Proceedings",

publisher = "Institute of Electrical and Electronics Engineers",

address = "United States",

note = "25th Euromicro International Conference on Parallel, Distributed and Network-Based Processing (PDP 2017), PDP 2017 ; Conference date: 06-03-2017 Through 08-03-2017",

url = "https://www.pdp2017.org",

}

Mariano, A, Laarhoven, T & Bischof, C 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 2017, St. Petersburg, Russia, 6-8 March 2017 : Proceedings., 7912621, Institute of Electrical and Electronics Engineers, Piscataway, pp. 23-30, 25th Euromicro International Conference on Parallel, Distributed and Network-Based Processing (PDP 2017), St. Petersburg, Russian Federation, 6/03/17. https://doi.org/10.1109/PDP.2017.60

A parallel variant of LDSieve for the SVP on lattices. / Mariano, Artur; Laarhoven, Thijs; Bischof, Christian.

2017 25th Euromicro International Conference on Parallel, Distributed and Network-Based Processing, PDP 2017, St. Petersburg, Russia, 6-8 March 2017 : Proceedings. Piscataway : Institute of Electrical and Electronics Engineers, 2017. p. 23-30 7912621.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - A parallel variant of LDSieve for the SVP on lattices

AU - Mariano, Artur

AU - Laarhoven, Thijs

AU - Bischof, Christian

N1 - Conference code: 25

PY - 2017/4/26

Y1 - 2017/4/26

N2 - 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.

AB - 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.

KW - hashsieve

KW - lattices cryptography

KW - multi-core

KW - parallel

UR - http://www.scopus.com/inward/record.url?scp=85019608089&partnerID=8YFLogxK

U2 - 10.1109/PDP.2017.60

DO - 10.1109/PDP.2017.60

M3 - Conference contribution

AN - SCOPUS:85019608089

SN - 978-1-5090-6059-7

SP - 23

EP - 30

BT - 2017 25th Euromicro International Conference on Parallel, Distributed and Network-Based Processing, PDP 2017, St. Petersburg, Russia, 6-8 March 2017 : Proceedings

PB - Institute of Electrical and Electronics Engineers

CY - Piscataway

T2 - 25th Euromicro International Conference on Parallel, Distributed and Network-Based Processing (PDP 2017)

Y2 - 6 March 2017 through 8 March 2017

ER -

Mariano A, Laarhoven T, Bischof C. A parallel variant of LDSieve for the SVP on lattices. In 2017 25th Euromicro International Conference on Parallel, Distributed and Network-Based Processing, PDP 2017, St. Petersburg, Russia, 6-8 March 2017 : Proceedings. Piscataway: Institute of Electrical and Electronics Engineers. 2017. p. 23-30. 7912621 https://doi.org/10.1109/PDP.2017.60