Welcome to the resource topic for 2023/237
Title:
Fast Practical Lattice Reduction through Iterated Compression
Authors: Keegan Ryan, Nadia Heninger
Abstract:We introduce a new lattice basis reduction algorithm with approximation guarantees analogous to the LLL algorithm and practical performance that far exceeds the current state of the art. We achieve these results by iteratively applying precision management techniques within a recursive algorithm structure and show the stability of this approach. We analyze the asymptotic behavior of our algorithm, and show that the heuristic running time is O(n^{\omega}(C+n)^{1+\varepsilon}) for lattices of dimension n, \omega\in (2,3] bounding the cost of size reduction, matrix multiplication, and QR factorization, and C bounding the log of the condition number of the input basis B. This yields a running time of O\left(n^\omega (p + n)^{1 + \varepsilon}\right) for precision p = O(\log \|B\|_{max}) in common applications. Our algorithm is fully practical, and we have published our implementation. We experimentally validate our heuristic, give extensive benchmarks against numerous classes of cryptographic lattices, and show that our algorithm significantly outperforms existing implementations.
ePrint: https://eprint.iacr.org/2023/237
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 .