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 BZn×n and returns a (reduced) basis C of the Euclidean lattice L spanned by B, whose first vector satisfies ||c1||(1+c)(4/3)(n1)/4(detL)1/n for any fixed c>0. It terminates within O(n4+ϵβ1+ϵ) bit operations for any ϵ>0, with β=logmaxi||bi||. 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},
      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.