Paper 2016/852

Faster LLL-type Reduction of Lattice Bases

Arnold Neumaier and Damien Stehle

Abstract

We describe an asymptotically fast variant of the LLL lattice reduction algorithm. It takes as input a basis $\mathbf B \in \mathbb Z^{n \times n}$ and returns a (reduced) basis $\mathbf C$ of the Euclidean lattice $L$ spanned by $\mathbf B$, whose first vector satisfies $||\mathbf c_1|| \leq (1+c)(4/3)^{(n-1)/4} \cdot (\det L)^{1/n}$ for any fixed $c>0$. It terminates within $O(n^{4+\epsilon} \beta^{1+\epsilon})$ bit operations for any $\epsilon >0$, with $\beta = \log \max_i ||\mathbf b_i||$. It does rely on fast integer arithmetic but does not make use of fast matrix multiplication.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. ISSAC 2016
Contact author(s)
damien stehle @ gmail com
History
2016-09-07: received
Short URL
https://ia.cr/2016/852
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/852,
      author = {Arnold Neumaier and Damien Stehle},
      title = {Faster LLL-type Reduction of Lattice Bases},
      howpublished = {Cryptology ePrint Archive, Paper 2016/852},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/852}},
      url = {https://eprint.iacr.org/2016/852}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.