Abstract
We propose a recursive lattice reduction framework for finding short non-zero vectors or dense sublattices of a lattice. The framework works by recursively searching for dense sublattices of dense sublattices (or their duals) with progressively lower rank. When the procedure encounters a recursive call on a lattice L with relatively low rank, we simply use a known algorithm to find a shortest non-zero vector in L.
This new framework is complementary to basis reduction algorithms, which similarly work to reduce an n-dimensional lattice problem with some approximation factor γ to a lower-dimensional exact lattice problem in some lower dimension k, with a tradeoff between γ, n, and k. Our framework provides an alternative and arguably simpler perspective. For example, our algorithms can be described at a high level without explicitly referencing any specific basis of the lattice, the Gram-Schmidt orthogonalization, or even projection (though, of course, concrete implementations of algorithms in this framework will likely make use of such things).
We present a number of instantiations of our framework. Our main concrete result is an efficient reduction that matches the tradeoff achieved by the best-known basis reduction algorithms. This reduction also can be used to find dense sublattices with any rank ℓ satisfying min{ℓ,n−ℓ}≤n−k+1, using only an oracle for SVP in k dimensions, with slightly better parameters than what was known using basis reduction.
We also show a simple reduction with the same tradeoff for finding short vectors in quasipolynomial time, and a reduction from finding dense sublattices of a high-dimensional lattice to this problem in lower dimension. Finally, we present an automated search procedure that finds algorithms in this framework that (provably) achieve better approximations with fewer oracle calls.