New Results on Lattice Reduction Algorithms using Deep Insertions

A lattice is generated by integer linear combinations of a finite set of linearly independent vectors constituting a basis. A lattice reduction algorithm takes as input a bad basis and provides as output a reduced basis with shorter and more orthogonal vectors. Lattice reduction has many applications, including the cryptanalysis of lattice-based post-quantum cryptographic systems. This thesis proposes novel lattice reduction algorithms, their theoretical analyses, implementations and experimental comparisons with a variety of algorithms.

LLL and its improvements are among the most efficient lattice reduction algorithms, while BKZ and its improvements provide the strongest reductions. The DeepLLL algorithm introduced alongside BKZ uses the technique of deep insertions to reorder the basis vectors. DeepLLL improves the output quality of LLL but is known to be significantly slower. In fact, despite the lack of theoretical analysis, the common belief is that the runtime of DeepLLL is superpolynomial while some also believe that it is superexponential. In contrast, analysis of BKZ shows that its runtime is exponential in the blocksize.

The main results of this thesis are as follows. As a first, an asymptotic runtime efficiency analysis of DeepLLL has been conducted for the first time in more than 30 years. A generalisation of lattice reduction algorithms using deep insertions (DeepLLL, Pot-LLL and SS-LLL) is described, showing that these algorithms improve a measure of quality of the basis, allowing for a more cohesive understanding of these algorithms. Thereafter, a novel framework of greedy algorithms called X-GG is proposed, based on deep insertions using a general measure X of basis quality. The framework is instantiated with two global measures of basis quality - potential (Pot) and squared sum (SS).

The X-GG framework is further extended for a localised sublattice measure, providing a new algorithm based on the Lov\'asz condition (LC), called LC-GG. A variant of this algorithm called LC-GG-α restricts the deep insertions to blocks of α vectors. LC-GG-α generally returns shorter vectors than BKZ-β when α = β, the first LLL-type algorithm to do so. LC-GG also compares favourably in terms of runtime with the original BKZ algorithm. A recursive generalisation of X-GG called X-PGG uses a novel partitioning technique - a first using deep insertions - to improve the runtime of X-GG at small dimensions, without compromising on output quality. The deep insertions in an iteration of this algorithm can potentially be parallelised for further improvement in its runtime.

For all new algorithms, we provide (1) proofs of correctness assuming rational arithmetic, (2) theoretical notions of reducedness, (3) theoretical bounds on runtime, (4) theoretical bounds on output quality (except when the measure is SS), and (5) extensive experimental analysis to compare their runtime efficiency and output quality, especially with BKZ.