Recursive Lattice Reduction

Recursive Lattice Reduction

Abstract:  We propose a new framework called recursive lattice reduction for finding short non-zero vectors in a lattice or for finding dense sublattices of a lattice. At a high level, the framework works by recursively searching for dense sublattices of dense sublattices (or their duals) with progressively lower rank. We view this new framework as complementary to basis reduction algorithms; it provides an alternative and arguably simpler perspective which can be described without explicitly referencing any specific basis of the lattice.
Our main concrete result is an efficient reduction from the approximate Densest Sublattice Problem to exact (Hermite) Shortest Vector Problem in dimension k that matches the tradeoff between k, input dimension n, and approximation factor \gamma achieved by the best-known basis reduction algorithms (in terms of the Hermite factor, up to low-order terms) across all parameter regimes. In fact, this reduction also can be used to find dense sublattices with relatively large rank, which is a novel result (as far as we know). Additionally, we present an automated approach for searching for algorithms in this framework that (provably) achieve better approximations with fewer oracle calls.
 

Bio: Spencer Peters is a 5th year PhD student in Cornell CIS, advised by Noah Stephens-Davidowitz. He is broadly interested in the intersection of cryptography and algorithms, with a particular focus on lattice algorithms.