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.
Liste complète des métadonnées

Littérature citée [19 références]  Voir  Masquer  Télécharger

https://hal-ens-lyon.archives-ouvertes.fr/ensl-00993445
Contributeur : Gilles Villard <>
Soumis le : lundi 5 septembre 2016 - 08:50:21
Dernière modification le : mardi 24 avril 2018 - 13:52:47
Document(s) archivé(s) le : mardi 6 décembre 2016 - 12:59:06

Fichier

lift.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Goel Sarushi, Ivan Morel, Damien Stehlé, Gilles Villard. LLL reducing with the most significant bits. 2016. 〈ensl-00993445〉

Partager

Métriques

Consultations de la notice

550

Téléchargements de fichiers

101