Léo Ducas
CWI, Cryptology Group and Mathematical Institute, Leiden University, The Netherlands

Ludo N. Pulles
CWI, Cryptology Group, The Netherlands

Marc Stevens
CWI, Cryptology Group, The Netherlands

Keywords: Lattice reduction, LLL, Segmentation, Parallelism, Concrete performance, Divide and Conquer

Abstract

We propose BLASter, a proof of concept LLL implementation that demonstrates the practicality of multiple theoretical improvements. The implementation uses the segmentation strategy from Neumaier–Stehlé (ISSAC 2016), parallelism and Seysen's reduction that was proposed by Kirchner–Espitau–Fouque (CRYPTO 2021) and implemented in OptLLL, and the BLAS library for linear algebra operations. It consists of only 1000 significant lines of C++ and Python code, and is made publicly available.

For q-ary lattices that fplll can handle without multiprecision (dimension <180), BLASter is considerably faster than fplll, OptLLL and Ryan–Heninger's flatter (CRYPTO 2023), without degrading output reduction quality. Thanks to Seysen's reduction it can further handle larger dimension without resorting to multiprecision, making it more than 10x faster than flatter and OptLLL, and 100x faster than fplll in dimensions 256 to 1024.

It further includes segmented BKZ and segmented deep-LLL variants. The latter provides bases as good as BKZ-15 and has a runtime that is only a couple of times more than our LLL baseline.

This remains a proof of concept: the effective use of higher precision — which is needed to handle lattices — has further obstacles and is left for future work. Still, this work contains many lessons learned, and is meant to motivate and guide the development of a robust and modern lattice reduction library, which shall be much faster than fplll.