Paper 2023/261

A Greedy Global Framework for LLL

Abstract

LLL-style lattice reduction algorithms iteratively employ size reduction and reordering on ordered basis vectors to find progressively shorter, more orthogonal vectors. These algorithms work with a designated measure of basis quality and perform reordering by inserting a vector in an earlier position depending on the basis quality before and after reordering. DeepLLL was introduced alongside the BKZ reduction algorithm, however the latter has emerged as the state-of-the-art and has therefore received greater attention. We first show that LLL-style algorithms iteratively improve a basis quality measure; specifically that DeepLLL improves a sublattice measure based on the generalised Lovász condition. We then introduce a new generic framework for lattice reduction algorithms, working with some quality measure X. We instantiate our framework with two quality measures - basis potential (Pot) and squared sum (SS) - both of which have corresponding DeepLLL algorithms. We prove polynomial runtimes for our X-GGLLL algorithms and guarantee their output quality. We run two types of experiments (implementations provided publicly) to compare performances of LLL, X-DeepLLL, X-GGLLL; with multi-precision arithmetic using overestimated floating point precision for standalone comparison with no preprocessing, and with standard datatypes using LLL-preprocessed inputs. In preprocessed comparison, we also compare with BKZ. In standalone comparison, our GGLLL algorithms produce better quality bases whilst being much faster than the corresponding DeepLLL versions. The runtime of SS-GGLLL is only second to LLL in our standalone comparison. SS-GGLLL is significantly faster than the FPLLL implementation of BKZ-12 at all dimensions and outputs better quality bases dimensions 100 onward.