Faster Lattice Enumeration
This work addresses a computational bottleneck in lattice-based cryptography, offering a significant speedup for solving shortest vector problems, though it appears incremental as it builds on existing methods like extreme pruning.
The paper tackles the problem of speeding up lattice enumeration for finding shortest vectors by introducing obtuse bases, showing that any lattice basis can be transformed into an obtuse basis in O(n^4) time, which makes enumeration exponentially faster and allows integration with extreme pruning.
A lattice reduction is an algorithm that transforms the given basis of the lattice to another lattice basis such that problems like finding a shortest vector and closest vector become easier to solve. Some of the famous lattice reduction algorithms are LLL and BKZ reductions. We define a class of bases called \emph{obtuse bases} and show that any lattice basis can be transformed to an obtuse basis in $\mathcal{O}(n^4)$ time. A shortest vector s can be written as $v_1b_1+\cdots+v_nb_n$ where $b_1,\dots,b_n$ are the input basis vectors and $v_1,\dots,v_n$ are integers. When the input basis is obtuse, all these integers can be chosen to be positive for a shortest vector. This property of the obtuse basis makes lattice enumeration algorithm for finding a shortest vector exponentially faster. Moreover, extreme pruning, the current fastest algorithm for lattice enumeration, can be run on an obtuse basis.