Cryptology ePrint Archive: Report 2021/141

Advanced Lattice Sieving on GPUs, with Tensor Cores

Léo Ducas and 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.

Category / Keywords: public-key cryptography / Lattice Sieving, Shortest Vector, G6K, Cryptanalysis, Challenges.

Date: received 9 Feb 2021, last revised 9 Feb 2021

Contact author: leo ducas at cwi nl, Wessel van Woerden@cwi nl, marc stevens@cwi nl

Available format(s): PDF | BibTeX Citation

Version: 20210210:073647 (All versions of this report)

Short URL: ia.cr/2021/141


[ Cryptology ePrint archive ]