inria-00211875, version 2
Worst-Case Hermite-Korkine-Zolotarev Reduced Lattice Bases
Guillaume Hanrot
a, 1Damien Stehlé b, 2
N° RR-6422 (2008)
Résumé : The Hermite-Korkine-Zolotarev reduction plays a central role in strong lattice reduction algorithms. By building upon a technique introduced by Ajtai, we show the existence of Hermite-Korkine-Zolotarev reduced bases that are arguably least reduced. We prove that for such bases, Kannan's algorithm solving the shortest lattice vector problem requires~$d^{\frac{d}{2\e}(1+o(1))}$ bit operations in dimension~$d$. This matches the best complexity upper bound known for this algorithm. These bases also provide lower bounds on Schnorr's constants~$\alpha_d$ and~$\beta_d$ that are essentially equal to the best upper bounds. Finally, we also show the existence of particularly bad bases for Schnorr's hierarchy of reductions.
- a – INRIA
- b – CNRS
- 1 : CACAO (Courbes, Algèbre, Calculs, Arithmétique des Ordinateurs) (INRIA Lorraine - LORIA)
- CNRS : UMR7503 – INRIA – Université Henri Poincaré - Nancy I – Université Nancy II – Institut National Polytechnique de Lorraine
- 2 : ARENAIRE (Inria Grenoble Rhône-Alpes / LIP Laboratoire de l'Informatique du Parallélisme)
- INRIA – CNRS : UMR5668 – Université Claude Bernard - Lyon I – École Normale Supérieure - Lyon
- Domaine : Informatique/Complexité
Informatique/Cryptographie et sécuritéMathématiques/Théorie des nombres - Mots-clés : Lattice basis reduction – shortest vector problem – HKZ-reduction – BKZ-reduction
- Référence interne : RR-6422
- Versions disponibles : v1 (22-01-2008) v2 (24-01-2008)
- inria-00211875, version 2
- http://hal.inria.fr/inria-00211875
- oai:hal.inria.fr:inria-00211875
- Contributeur : Rapport De Recherche Inria
- Soumis le : Jeudi 24 Janvier 2008, 16:12:59
- Dernière modification le : Mercredi 5 Mars 2008, 09:49:36
Documents associés
Exporter