Parallel (probable) lock-free hash sieve: a practical sieving algorithm for the SVP

A. Mariano, C. Bischof, T. Laarhoven

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

21 Citaten (Scopus)

Samenvatting

In this paper, we assess the practicability of Hash Sieve, a recently proposed sieving algorithm for the Shortest Vector Problem (SVP) on lattices, on multi-core shared memory systems. To this end, we devised a parallel implementation that scales well, and is based on a probable lock-free system to handle concurrency. The probable lock-free system, implemented with spin-locks, in turn implemented with CAS operations, becomes likely a lock-free mechanism, since threads block only when strictly required and chances are that they are not required to block. With our implementation, we were able to solve the SVP on an arbitrary lattice in dimension 96, in less than 17.5 hours, using 16 physical cores. The least squares fit of the execution times of our implementation, in seconds, lies between 2(0.32n - 15) or 2(0.33n - 16). These results are of paramount importance for the selection of parameters in lattice-based cryptography, as they indicate that sieving algorithms are way more practical for solving the SVP than previously believed.

Originele taal-2Engels
Titel2015 44th International Annual Conference on Parallel Processing, ICPP 2015, 1-4 September 2015, Bejing, China
Plaats van productiePiscataway
UitgeverijInstitute of Electrical and Electronics Engineers
Pagina's590-599
Aantal pagina's10
ISBN van elektronische versie978-1-4673-7587-0
DOI's
StatusGepubliceerd - 8 dec 2015
Evenement44th International Conference on Parallel Processing (ICPP 2015), September 1-4, 2015, Beijing, China - Beijing, China
Duur: 1 sep 20154 sep 2015

Congres

Congres44th International Conference on Parallel Processing (ICPP 2015), September 1-4, 2015, Beijing, China
Verkorte titelICPP 2015
LandChina
StadBeijing
Periode1/09/154/09/15

Vingerafdruk Duik in de onderzoeksthema's van 'Parallel (probable) lock-free hash sieve: a practical sieving algorithm for the SVP'. Samen vormen ze een unieke vingerafdruk.

Citeer dit