Random Sampling Reduction with Precomputation

摘要

Given an integer n-dimensional lattice basis, the random sampling reduction was proven to find a short vector in O(n~2(k/6)~(k/4)) arithmetic steps with an integer k, which is freely chosen by users. This paper introduces new random sampling reduction using precomputation techniques. The computation cost O(k~2 log~2 k(k/6)~(k/4) + nk log k) is almost independent of the lattice dimension number. The new method is therefore especially advantageous to find a short lattice vector in higher dimensions. The arithmetic operation number of our new method is about 20 of the random sampling reduction with 200 dimensions, and with 1000 dimensions it is less than 1 (≈ 1/130) of that of the random sampling reduction with representative parameter settings under reasonable assumptions.