LLL reducing with the most significant bits

Saruchi, Ivan Morel, Damien Stehlé and Gilles Villard

Abstract: Let B be a basis of a Euclidean lattice, and ~B an approximation thereof. We give a sufficient condition on the closeness between ~B and B so that an LLL-reducing transformation U for ~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 efficiently batching LLL reductions for closely related inputs.

Download: pdf.