Abstract:
Lattice reduction is a hard problem of interest to both public-key
cryptography and cryptanalysis. Despite its importance, extremely
few algorithms are known. The best algorithm known in high dimension
is due to Schnorr, proposed in 1987 as a block generalization of the
famous LLL algorithm. This paper deals with Schnorr's algorithm and
potential improvements. We prove that Schnorr's algorithm outputs
better bases than what was previously known: namely, we decrease all
former bounds on Schnorr's approximation factors to their (ln 2)-th
power. On the other hand, we also show that the output quality may
have intrinsic limitations, even if an improved reduction strategy
was used for each block, thereby strengthening recent results by Ajtai.
This is done by making a connection between Schnorr's algorithm and
a mathematical constant introduced by Rankin more than 50 years ago
as a generalization of Hermite's constant. Rankin's constant leads
us to introduce the so-called smallest volume problem, a new lattice
problem which generalizes the shortest vector problem, and which has
applications to blockwise lattice reduction generalizing LLL and Schnorr's
algorithm, possibly improving their output quality. Schnorr's algorithm
is actually based on an approximation algorithm for the smallest volume
problem in low dimension. We obtain a slight improvement over Schnorr's
algorithm by presenting a cheaper approximation algorithm for the
smallest volume problem, which we call transference reduction.
Bibtex:
@inproceedings{GHKN06,
author = {Nicolas Gama and
Nick Howgrave-Graham and
Henrik Koy and
Phong Q. Nguyen},
title = {Rankin's Constant and Blockwise Lattice Reduction},
pages = {112-130},
booktitle = "Advances in Cryptology -- Proceedings of CRYPTO '06",
publisher = {Springer},
series = {Lecture Notes in Computer Science},
volume = "4117",
year = 2006
}