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.
Complete list of metadatas

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 : Tuesday, April 23, 2019 - 10:18:43 AM
Long-term archiving on : 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. 39th International Symposium on Symbolic and Algebraic Computation, Kobe, Japan, July 23-25, 2014, Jul 2014, Kobe, Japan. ⟨10.1145/2608628.2608645⟩. ⟨ensl-00993445⟩

Share

Metrics

Record views

823

Files downloads

189