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