2021-06-16
Advanced lattice sieving on GPUs, with Tensor Cores
Publication
Publication
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.
| Additional Metadata | |
|---|---|
| , , , , | |
| doi.org/10.1007/978-3-030-77886-6_9 | |
| Lecture Notes in Computer Science | |
| PRivacy preserving pOst-quantuM systEms from advanced crypTograpHic mEchanisms Using latticeS , A Reduction Theory for Codes and Lattices in Cryptography , Algebraic Methods for Stronger Crypto , Cryptanalysis of Lattice-based Cryptography | |
| Advances in Cryptology - EUROCRYPT 2021 | |
| , , , | |
| Organisation | Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands |
|
Ducas, L., Stevens, M., & van Woerden, W. (2021). Advanced lattice sieving on GPUs, with Tensor Cores. In Proceedings of EUROCRYPT 2021 (pp. 249–279). doi:10.1007/978-3-030-77886-6_9 |
|
