Paper 2024/1681
Another L makes it better? Lagrange meets LLL and may improve BKZ pre-processing
Abstract
We present a new variant of the LLL lattice reduction algorithm, inspired by Lagrange notion of pair-wise reduction, called L4. Similar to LLL, our algorithm is polynomial in the dimension of the input lattice, as well as in $\log M$, where $M$ is an upper-bound on the norm of the longest vector of the input basis. We experimentally compared the norm of the first basis vector obtained with LLL and L4 up to dimension 200. On average we obtain vectors that are up to $16\%$ shorter. We also used our algorithm as a pre-processing step for the BKZ lattice reduction algorithm with blocksize 24. In practice, up to dimension 140, this allows us to reduce the norm of the shortest basis vector on average by $3\%$, while the runtime does not significantly increases. In $10\%$ of our tests, the whole process was even faster.
Metadata
- Available format(s)
-
PDF
- Publication info
- Published elsewhere. Minor revision. ALENEX2025
- Contact author(s)
-
sebastien balny @ u-picardie fr
claire delaplace @ u-picardie fr
gilles dequen @ u-picardie fr - History
- 2024-10-18: approved
- 2024-10-16: received
- See all versions
- Short URL
- https://ia.cr/2024/1681
- License
-
CC BY-NC
BibTeX
@misc{cryptoeprint:2024/1681,
author = {Sebastien Balny and Claire Delaplace and Gilles Dequen},
title = {Another L makes it better? Lagrange meets {LLL} and may improve {BKZ} pre-processing},
howpublished = {Cryptology {ePrint} Archive, Paper 2024/1681},
year = {2024},
url = {https://eprint.iacr.org/2024/1681}
}