LLL reducing with the most significant bits

Abstract : Let B be a basis of a Euclidean lattice, and \tilde{B} an approximation thereof. We give a sufficient condition on the closeness between \tilde{B} and B so that an LLL-reducing transformation U for \tilde{B} remains valid for B. Further, we analyse an efficient reduction algorithm when B is itself a small deformation of an LLL-reduced basis. Applications include speeding-up reduction by keeping only the most significant bits of B, reducing a basis that is only approximately known, and effi- ciently batching LLL reductions for closely related inputs.
Liste complète des métadonnées

Cited literature [19 references]  Display  Hide  Download

https://hal-ens-lyon.archives-ouvertes.fr/ensl-00993445
Contributor : Gilles Villard <>
Submitted on : Monday, September 5, 2016 - 8:50:21 AM
Last modification on : Thursday, February 7, 2019 - 4:05:40 PM
Document(s) archivé(s) le : Tuesday, December 6, 2016 - 12:59:06 PM

File

lift.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Goel Sarushi, Ivan Morel, Damien Stehlé, Gilles Villard. LLL reducing with the most significant bits. ISSAC'14, International Symposium on Symbolic and Algebraic Computation, Jul 2014, Kobe, Japan. 2014, 〈10.1145/2608628.2608645〉. 〈ensl-00993445〉

Share

Metrics

Record views

682

Files downloads

130