Welcome to the resource topic for 2023/261
Title:
A Greedy Global Framework for LLL
Authors: Sanjay Bhattacherjee, Julio Hernandez-Castro, Jack Moyler
Abstract:LLL-style lattice reduction algorithms employ two operations on ordered basis vectors - size reduction and reordering - to improve the basis quality by iteratively finding shorter and more orthogonal vectors. These algorithms typically have two design features. First, they work with a local or global measure of basis quality. Second, they reorder a subset of the basis vectors based on the basis quality before and after reordering. In this work, we introduce a new generic framework for designing lattice reduction algorithms. An algorithm in the framework makes greedy basis reordering choices globally on the whole basis in every iteration, based on a measure of basis quality. The greedy choice allows to attain the desired quality very quickly making the algorithms extremely efficient in practice. The framework is instantiated using two quality measures (1) the potential of the basis, and (2) the squared sum of its Gram-Schmidt orthogonalised vectors, to get two new basis reduction algorithms. We prove that both algorithms run in polynomial time and provide quality guarantees on their outputs. Our squared sum based algorithm has runtime close to LLL while outperforming BKZ-12 in output quality at higher dimensions. We have made our implementations and the experimental results public.
ePrint: https://eprint.iacr.org/2023/261
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 .