Paper 2021/141

Advanced Lattice Sieving on GPUs, with Tensor Cores

Léo Ducas, Marc Stevens, and Wessel van Woerden

Abstract

In this work, we study GPU implementations of various state-of-the-art sieving algorithms for lattices (Becker-Gama-Joux 2015, Becker-Ducas-Gama-Laarhoven 2016, Herold-Kirshanova 2017) inside the General Sieve Kernel (G6K, Albrecht et al. 2019). In particular, we extensively exploit the recently introduced *Tensor Cores* -- originally designed for raytracing and machine learning -- and demonstrate their fitness for the cryptanalytic task at hand. We also propose a new *dual-hash* technique for efficient detection of `lift-worthy' pairs to accelerate a key ingredient of G6K: finding short lifted vectors. We obtain new computational records, reaching dimension $180$ for the SVP Darmstadt Challenge improving upon the previous record for dimension $155$. This computation ran for $51.6$ days on a server with $4$ NVIDIA Turing GPUs and $1.5$TB of RAM. This corresponds to a gain of about two orders of magnitude over previous records both in terms of wall-clock time and of energy efficiency.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Lattice SievingShortest VectorG6KCryptanalysisChallenges.
Contact author(s)
leo ducas @ cwi nl
Wessel van Woerden @ cwi nl
marc stevens @ cwi nl
History
2021-02-10: received
Short URL
https://ia.cr/2021/141
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/141,
      author = {Léo Ducas and Marc Stevens and Wessel van Woerden},
      title = {Advanced Lattice Sieving on GPUs, with Tensor Cores},
      howpublished = {Cryptology ePrint Archive, Paper 2021/141},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/141}},
      url = {https://eprint.iacr.org/2021/141}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.