International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: Advanced Lattice Sieving on GPUs, with Tensor Cores

Authors:
Léo Ducas , CWI, Amsterdam
Marc Stevens , CWI, Amsterdam
Wessel van Woerden , CWI, Amsterdam
Download:
Search ePrint
Search Google
Conference: EUROCRYPT 2021
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.5TB 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.
BibTeX
@inproceedings{eurocrypt-2021-30941,
  title={Advanced Lattice Sieving on GPUs, with Tensor Cores},
  publisher={Springer-Verlag},
  author={Léo Ducas and Marc Stevens and Wessel van Woerden},
  year=2021
}