Skip to Main content Skip to Navigation
Conference papers

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 metadata

Cited literature [19 references]  Display  Hide  Download

https://hal-ens-lyon.archives-ouvertes.fr/ensl-00993445
Contributor : Gilles Villard Connect in order to contact the contributor
Submitted on : Monday, September 5, 2016 - 8:50:21 AM
Last modification on : Saturday, September 11, 2021 - 3:18:28 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

997

Files downloads

396