Worst-Case Hermite-Korkine-Zolotarev Reduced Lattice Bases

Guillaume Hanrot and Damien Stehlé

Abstract: Euclidean lattice reduction is a representation paradigm: a basis is well-reduced if information relevant to the lattice is easily tractable from it. The notion of Hermite-Korkine-Zolotarev reduction is the best known today. It plays a central role in most euclidean lattice strong 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 possible. This draws precisely the limits of the realm of the Hermite-Korkine-Zolotarev reduction. We prove that for such bases, Kannan's algorithm solving the shortest lattice vector problem requires at least d^(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(k) and beta(k) that are essentially equal to the best upper bounds. These constants quantify the effectiveness of Schnorr's hierarchy of reductions. Finally, we also derive from Ajtai's technique the existence of particularly bad bases for Schnorr's hierarchy of algorithms.

Download: pdf.