Paper 2021/430

Lattice Enumeration on GPUs for fplll

Simon Pohmann, Marc Stevens, and Jens Zumbrägel

Abstract

The Kannan-Fincke-Pohst lattice enumeration algorithm is the classical method for solving the shortest vector problem in lattices. It is also a fundamental tool for most lattice reduction algorithms that provide speed-length tradeoffs. As this algorithm allows efficient parallel implementations, it is likely that implementing it on modern graphics processing units (GPUs) can significantly improve performance. We provide such an implementation that is compatible with the fplll lattice reduction library [fplll16] and achieves a considerable speedup in higher lattice dimensions, compared to current, multithreaded versions. For this, we use the CUDA technology that provides an abstract language for programming GPUs. [fplll16] The FPLLL development team. “fplll, a lattice reduction library”. 2016. URL: https://github.com/fplll/fplll

Note: The benchmark claimed to include pruning did not include it. I have updated the benchmark graphic and some of the explanation concerning pruning.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. Minor revision.
Keywords
Lattice EnumerationShortest VectorfplllCryptanalysis
Contact author(s)
simon @ pohmann de
History
2021-07-30: revised
2021-04-06: received
See all versions
Short URL
https://ia.cr/2021/430
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/430,
      author = {Simon Pohmann and Marc Stevens and Jens Zumbrägel},
      title = {Lattice Enumeration on GPUs for fplll},
      howpublished = {Cryptology ePrint Archive, Paper 2021/430},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/430}},
      url = {https://eprint.iacr.org/2021/430}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.