Optimization of Search Space for Finding Very Short Lattice Vectors

Shortest vector problem on lattices (SVP) is a well-known algorithmic combinatorial problem. The hardness of SVP is a foundation for the security of Lattice-based cryptography, which is a promising candidate of the post-quantum cryptographic algorithms. Therefore, many works have focused on the estimation of the hardness of SVP and the construction of efficient algorithms. Recently, a probabilistic approach has been proposed for estimating the hardness, which is based on the randomness assumption. The approach can estimate quite accurately the distribution of very short lattice vectors in a search space. In this paper, a new method is proposed for optimizing a box-type search space in random sampling by this probabilistic approach. It has been known empirically that the tail part of the search space should be more intensively explored for finding very short lattice vectors efficiently. However, it was difficult to adjust the search space quantitatively. On the other hand, our proposed method can find the best search space approximately. Experimental results show that our method is useful when the lattice basis is small or already reduced in advance.