Obtuse Lattice Bases
This work addresses a computational bottleneck in lattice-based cryptography and algorithms, offering a potential speedup for solving lattice problems, though it appears incremental as it builds on existing lattice reduction methods.
The paper tackles the problem of finding shortest vectors in lattices by introducing obtuse bases, which allow all integer coefficients in the representation of a shortest vector to be positive, making lattice enumeration exponentially faster. The authors implemented and tested the algorithm on small bases.
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. We define a class of bases called obtuse bases and show that any lattice basis can be transformed to an obtuse basis. A shortest vector $\mathbf{s}$ can be written as $\mathbf{s}=v_1\mathbf{b}_1+\dots+v_n\mathbf{b}_n$ where $\mathbf{b}_1,\dots,\mathbf{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 obtuse bases makes the lattice enumeration algorithm for finding a shortest vector exponentially faster. We have implemented the algorithm for making bases obtuse, and tested it some small bases.