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.
Homepage