Improved Lattice Reduction Algorithms on Lattices of Small Determinants

The lattice reduction algorithm (LRA) takes as inputs a basis of lattice and outputs a relatively short vector up to Hermite factor multiplication. The worst case of Hermite factor of known LRAs has an exponential size to the rank of the given lattice. In this paper, we present a sublattice technique for improving the performance of the LRA when an input integral lattice has a small determinant. The core idea involves application of the LRA to a sublattice of a determinant that is upper bounded by that of the whole lattice. As polynomial time is required to create the required sublattice, the entire complexity time of the algorithm is dominated by that of the applied LRA. Applying our technique to the Lenstra-- Lenstra--Lov{\'a}sz (LLL)algorithm on lattice $L$ of rank $n$ and $\det(L)\le 2^{ n^2/4}$, we obtain a lattice vector of size $\le 2^{\sqrt{\log\det L}+\frac{1}{16}}$. An interesting feature of our algorithm is that it becomes more useful as $\det L$ gets smaller; this is because the output size is dependent only on the $\det L$. For example, if $\det L=2^{n \sqrt n}$, the short vector outputted by our algorithm is of size $2^{n^{3/4}}$, which is sub-exponential in rank and significantly smaller than the size ($2^{n/4+\sqrt n}$) of the short vectors outputted by the LLL algorithm. Moreover , as an extension of the proposed algorithm, we obtained an improved result for the closest vector problem (CVP). The CVP algorithm provides alattice vector, whose distance to a target vector is approximately $2^{\sqrt{\log\det L}}$ times the distance between the target vector and the lattice $L$. The worst case factor of a known CVP is the exponential size of the rank; however, the result of the proposed algorithm on the lattice of a small determinant is the sub-exponential size of the rank