Welcome to the resource topic for 2024/1681
Title:
Another L makes it better? Lagrange meets LLL and may improve BKZ pre-processing
Authors: Sebastien Balny, Claire Delaplace, Gilles Dequen
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.
ePrint: https://eprint.iacr.org/2024/1681
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .