Probability analysis of SVP for low-dimensional cyclic generated lattice
Yuyun Chen, Gengran Hu · 2016
The hardness of Shortest Vector Problem (SVP) is the base for the security of some crypto schemes. SVP has been proved to be NP-hard under the randomized reductions. For general lattice, the bound for the basis integer coefficient of the shortest lattice vector is exponentially large, while the bound for the integer coefficient of SVP under its cyclic basis would be really small; the probability of the shortest vector's coefficients for the low-dimensional cyclic generated lattice is discussed. It implies that SVP over these lattices within constant steps can be solved.