21773 articles – 15587 Notices  [english version]

inria-00211875, version 2

Worst-Case Hermite-Korkine-Zolotarev Reduced Lattice Bases

Guillaume Hanrot () a, 1, Damien 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 (INRIA Lorraine - LORIA)
  • CNRS : UMR7503 – INRIA – Université Henri Poincaré - Nancy I – Université Nancy II – Institut National Polytechnique de Lorraine (INPL)
  • 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