Paper 2015/041

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

Artur Mariano, Thijs Laarhoven, and Christian Bischof

Abstract

In this paper, we assess the practicability of HashSieve, 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 and compare-and-swap operations, acts, likely, as a lock-free mechanism, since threads block only when strictly required and chances are that they are not required to block, because resource contention is very low. 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), which indicates that sieving algorithms are indeed way more practical than believed.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Minor revision. ICPP15
DOI
10.1109/ICPP.2015.68
Contact author(s)
artur mariano @ sc tu-darmstadt de
History
2016-03-09: last of 2 revisions
2015-01-17: received
See all versions
Short URL
https://ia.cr/2015/041
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/041,
      author = {Artur Mariano and Thijs Laarhoven and Christian Bischof},
      title = {Parallel (probable) lock-free HashSieve: a practical sieving algorithm for the SVP},
      howpublished = {Cryptology ePrint Archive, Paper 2015/041},
      year = {2015},
      doi = {10.1109/ICPP.2015.68},
      note = {\url{https://eprint.iacr.org/2015/041}},
      url = {https://eprint.iacr.org/2015/041}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.