Fast Practical Lattice Reduction through Iterated Compression

Keegan Ryan; Nadia Heninger

Paper 2023/237

Fast Practical Lattice Reduction through Iterated Compression

Keegan Ryan

, University of California, San Diego

Nadia Heninger

, University of California, San Diego

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 for lattices of dimension , bounding the cost of size reduction, matrix multiplication, and QR factorization, and bounding the log of the condition number of the input basis . This yields a running time of for precision 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.

Note: Full version. Includes new records for reducing an 8192-dimensional lattice basis.

Metadata

Available format(s): PDF
Category: Implementation
Publication info: A major revision of an IACR publication in CRYPTO 2023
Keywords: Lattice Reduction LLL Numerical Stability Lattice Attacks
Contact author(s): kryan @ ucsd edu
nadiah @ cs ucsd edu
History: 2023-06-09: revised; 2023-02-21: received; See all versions
Short URL: https://ia.cr/2023/237
License: CC BY

BibTeX

@misc{cryptoeprint:2023/237,
      author = {Keegan Ryan and Nadia Heninger},
      title = {Fast Practical Lattice Reduction through Iterated Compression},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/237},
      year = {2023},
      url = {https://eprint.iacr.org/2023/237}
}