Volume 4 (2008) Article 2 pp. 21-51

Optimal lower bounds for the Korkine-Zolotareff parameters of a lattice and for Schnorr's algorithm for the shortest vector problem

by Miklós Ajtai

Received: November 15, 2007
Published: May 10, 2008
DOI: 10.4086/toc.2008.v004a002

Download article from ToC site:
[PS (503K)]    [PS.GZ (147K)]    [PS.ZIP (147K)]
[PDF (296K)]    [DVI (252K)]    [TeX (110K)]
Misc.:
[HTML Bibliography] [Bibliography Source] [BibTeX] 
[About the Author(s)]
Keywords: approximation algorithm, lattice, shortest vector problem, geometry of numbers, basis reduction, LLL reduction, Schnorr's algorithm, Korkine-Zolotareff basis, random lattice
Categories: algorithms, approximation algorithms, lower bounds, lattice algorithms
ACM Classification: F.2.2, G.2, G.3
AMS Classification: 68Q25, 68W40, 68W25, 11H55, 11H99, 52C07, 60D05

Abstract: [Plain Text Version]

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 (2k)2n/k. (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, we prove the existence of a basis in n which is K-Z-reduced on all k-segments and where the ratio
| | b1 | | / shortest(L) is at least kcn/k. Noting that such a basis renders all versions of Schnorr's algorithm idle (output = input), it follows that the quantity kcn/k is a lower bound on the approximation ratio any version of Schnorr's algorithm can achieve on the shortest vector problem. This proves that Schnorr's analysis of the approximation ratio of his algorithm is optimal apart from the constant in the exponent. We also solve an open problem formulated by Schnorr about 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.