MergeLLL: A Hierarchical Divide-and-Conquer Framework for LLL-Based Lattice Reduction

Computer Science > Cryptography and Security [Submitted on 25 Jun 2026] MergeLLL: A Hierarchical Divide-and-Conquer Framework for LLL-Based Lattice Reduction Niharika Gauraha 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. Subjects: Cryptography and Security (cs.CR) Cite as: arXiv:2606.26784 [cs.CR]   (or arXiv:2606.26784v1 [cs.CR] for this version)   https://doi.org/10.48550/arXiv.2606.26784 Focus to learn more Submission history From: Niharika Gauraha [view email] [v1] Thu, 25 Jun 2026 09:20:03 UTC (144 KB) Access Paper: HTML (experimental) view license Current browse context: cs.CR < prev   |   next > new | recent | 2026-06 Change to browse by: cs References & Citations NASA ADS Google Scholar Semantic Scholar Export BibTeX Citation Bookmark Bibliographic Tools Bibliographic and Citation Tools Bibliographic Explorer Toggle Bibliographic Explorer (What is the Explorer?) Connected Papers Toggle Connected Papers (What is Connected Papers?) Litmaps Toggle Litmaps (What is Litmaps?) scite.ai Toggle scite Smart Citations (What are Smart Citations?) Code, Data, Media Demos Related Papers About arXivLabs Which authors of this paper are endorsers? | Disable MathJax (What is MathJax?)