Moduar Form Aprroach to Solving Lattice Problems.
Yuan Tian, Xueyong Zhu, Rongxin Sun · IACR Cryptology ePrint Archive · 2013
We construct new randomized algorithms to find the exact solutions to the shortest and closest vector problems (SVP and CVP) in Euclidean norm (`2) for integral lattices. Not only the minimal `2-norm of non-zero lattice vectors in SVP and the minimal `2-distance in CVP, but also how many lattice vectors reach those minimums can be simultaneously computed by the algorithms. Our approach is based on special properties of the generating function of lattice vectors’ `2-norms, the lattice-associated theta function, which is used in prior works mainly for hardness analysis on lattice problems but rarely for computational purposes. Such function’s modular properties are exploited to develop our SVP and CVP solvers. In computational complexity perspective and take our SVP solver as an example, for the integral lattice family {Λn} of dimension dimΛn = n and level hn = l(Λn) (the minimal positive integer such that the dual lattice Λn scaled by h 1/2 n is integral) polynomial in n, this algorithm can find the minimal `2-norm of non-zero lattice vectors and the number of such shortest vectors in Λn with success probability 1-e in the asymptotic space-complexity of polynomial in n and asymptotic time-complexity of nO(n) log(1/e). In addition, the only contribution to the algorithm’s exponential time complexity nO(n) log(1/e) comes from independently repeating a randomized lattice vector sampler nO(n) log(1/e) times. All the rest of operations contribute to the algorithm’s time-complexity only with an additive polynomial in n. Similar situations occur when solving the exact CVP by our algorithm. As a result, our solvers can be easily parallelized to be polynomial in time complexity, and a variant of our CVP solver can solve the closest vector problem with preprocessing (CVPP) in polynomial time and nO(n) log(1/e) space complexity.