LLL reducing with the most significant bits - Archive ouverte HAL Access content directly
Conference Papers Year : 2014

LLL reducing with the most significant bits

(1, 2) , (3, 2) , (3, 2) , (3, 2)
1
2
3

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.
Fichier principal
Vignette du fichier
lift.pdf (472.87 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

ensl-00993445 , version 1 (05-09-2016)

Identifiers

Cite

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⟩
578 View
155 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More