zbMATH — the first resource for mathematics

Lattice reduction by random sampling and birthday methods. (English) Zbl 1035.68113
Alt, Helmut (ed.) et al., STACS 2003. 20th annual symposium of theoretical aspects on computer science, Berlin, Germany, February 27 – March 1, 2003. Proceedings. Berlin: Springer (ISBN 3-540-00623-0/pbk). Lect. Notes Comput. Sci. 2607, 145-156 (2003).
Summary: We present a novel practical algorithm that, given lattice basis \(b_1,...,b_n\), finds in \(O(n^2 (\frac{k}{6})^{k/4})\) average time a shorter vector than \(b_{1}\) provided that \(b_{1}\) is \((\frac{k}{6})^{n/(2k)}\) times longer than the length of the shortest, nonzero lattice vector. We assume that the given basis \(b_1,\dots,b_n\) has an orthogonal basis that is typical for worst case lattice bases. The new reduction method samples short lattice vectors in high dimensional sublattices, it advances in sporadic big jumps. It decreases the approximation factor achievable in a given time by known methods to less than its fourth root. We further speed up the new method by the simple and the general birthday method.
For the entire collection see [Zbl 1017.00027].

68Q25 Analysis of algorithms and problem complexity
68P25 Data encryption (aspects in computer science)
68W25 Approximation algorithms
Full Text: Link