HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
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$ log $B)$. This worst-case complexity is problematic for lattices arising in cryptanalysis where $d$ or/and log $B$ 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$ + log $B$) log $B)$. This is the first LLL algorithm which running time provably grows only quadratically with respect to log $B$ 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 Connect in order to contact the contributor
Submitted on : Friday, May 19, 2006 - 9:01:32 PM
Last modification on : Friday, February 4, 2022 - 3:24:31 AM
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

108

Files downloads

368