Search papers, labs, and topics across Lattice.
This paper introduces MergeLLL, a hierarchical divide-and-conquer framework designed to enhance lattice basis reduction by employing a strategy inspired by merge sort. By splitting a lattice basis into sub-bases for independent local reductions, followed by a structured recombination process, the method achieves improved Gram-Schmidt orthogonality and numerical stability while reducing overall computational costs. Experimental results on subset-sum and NTRU-derived lattices show significant improvements over classical algorithms, including enhanced orthogonality and a better Hermite factor, indicating higher-quality reduced bases.
Achieving logarithmic parallel depth, MergeLLL significantly outperforms classical lattice reduction methods in both efficiency and quality of reduced bases.
Lattice basis reduction algorithms have various applications in computational number theory and lattice-based cryptography, but their complexity increases rapidly with the dimension. Motivated by the divide-and-conquer strategy of merge sort and incorporating PotLLL-style deep insertions during recombination, MergeLLL is proposed. In this framework, a lattice basis is split into sub-bases, local reductions are performed independently, and the full basis is reconstructed through hierarchical merging. The approach is focused on improving local lattice structure first before global basis properties are refined, resulting in enhanced Gram-Schmidt orthogonality and numerical stability, while overall computational cost is reduced. The method is naturally parallelizable, allowing efficient multicore and distributed execution. It is shown that the reduction and merging steps preserve the lattice structure through unimodular transformations and achieve logarithmic parallel depth. In experiments on subset-sum and NTRU-derived lattices, improvements over classical lattice reduction algorithms are demonstrated, including better orthogonality, a reduced number of expensive swap operations, and an improved Hermite factor, indicating higher-quality reduced bases.
