The worst-case behavior of Schnorr's algorithm approximating the shortest nonzero vector in a lattice

Abstract

Schnorr's algorithm for finding an approximation for the shortest nonzero vector in an n dimensional lattice depends on a parameter k. He proved that for a fixed k ≤ n his algorithm (block 2k-reduction) provides a lattice vector whose length is greater than the length of a shortest nonzero vector in the lattice by at most a factor of (4k2)n/k ft. (The time required by the algorithm depends on k.) We show that if k = o(n), this bound on the performance of Schnorr's algorithm cannot be improved (apart from a constant factor in the exponent), namely there is a lattice and a basis so that if they are given as an input to the algorithm then the resulting approximating factor of the output is at least kεn/k. (For larger integers k if Schnorr's algorithm runs in polynomial time then we have already a polynomial time algorithm for finding the shortest nonzero vector.) We also solve an open problem formulated by Schnorr about the the Korkine-Zolotareff lattice constants αk. We show that his upper bound αk ≤ k1+ln k is the best possible apart from a constant factor in the exponent. We prove a similar result about his upper bound βk, ≤ 4k2, where βk, is another lattice constant with an important role in Schnorr's analysis of his algorithm.