Techniques in Lattice Basis Reduction

Authors

  • Bal Kumar Khadka Author
  • Spyros S Magliveras Author

DOI:

https://doi.org/10.32674/hgbk7442

Keywords:

Lattice bases, unimodular matrices, right permutations, LLL algorithm, BKZ algorithm.

Abstract

The shortest vector  and closest vector  problems, presently considered intractable, are algorithmic tasks that lie at the core of many theoretical and applied problems. We investigate the efficacy of new optimization techniques to be used along with the LLL algorithm. The techniques we propose are: i) hill climbing and ii) lattice diffusion-sub lattice fusion . The first technique relies on the sensitivity of LLL to permutations of the input basis B, and optimization ideas over the symmetric group Σm and the second technique relies on partitioning the lattice into sublattices, performing basis reduction on the sublattice blocks, fusing the sublattices, and repeating. Our approach provides better results for finding shortest vectors, than LLL and other traditional methods.

Downloads

Published

2026-10-21