Skip to Main content Skip to Navigation
Reports

Floating-Point LLL Revisited

Phong Q. Nguyen Damien Stehlé 1
1 SPACES - Solving problems through algebraic computation and efficient software
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : Everybody knows the Lenstra-Lenstra-Lovász lattice basis reduction algorithm (LLL), which has proved invaluable in public-key cryptanalysis and in many other fields. Given an integer $d$-dimensional lattice basis which vectors have norms smaller than $B$, LLL outputs a so-called LLL-reduced basis in time $O(d^6 \log^3 B)$, using arithmetic operations on integers of bit-length $O(d \logB)$. This worst-case complexity is problematic for lattices arising in cryptanalysis where $d$ or/and $\logB$ are often large. As a result, the original LLL is almost never used in practice. Instead, one applies floating-point variants of LLL, where the long-integer arithmetic required by Gram-Schmidt orthogonalisation (central in LLL) is replaced by floating-point arithmetic. Unfortunately, this is known to be unstable in the worst-case: the usual floating-point LLL is not even guaranteed to terminate, and the output basis may not be LLL-reduced at all. In this article, we introduce the LLL$^2$ algorithm, a new and natural floating-point variant of LLL which provably outputs LLL-reduced bases in polynomial time $O(d^5 (d+\logB) \logB)$. This is the first LLL algorithm which running time provably grows only quadratically with respect to $\logB$ without fast integer arithmetic, like the famous Gaussian and Euclidean algorithms. The growth is cubic for all other LLL algorithms known.
Document type :
Reports
Complete list of metadata

https://hal.inria.fr/inria-00070616
Contributor : Rapport de Recherche Inria <>
Submitted on : Friday, May 19, 2006 - 9:01:32 PM
Last modification on : Friday, February 26, 2021 - 3:28:07 PM
Long-term archiving on: : Sunday, April 4, 2010 - 9:34:57 PM

Identifiers

  • HAL Id : inria-00070616, version 1

Collections

Citation

Phong Q. Nguyen, Damien Stehlé. Floating-Point LLL Revisited. [Research Report] RR-5387, INRIA. 2004, pp.28. ⟨inria-00070616⟩

Share

Metrics

Record views

173

Files downloads

477