Paper 2013/412

Moduar Form Aprroach to Solving Lattice Problems

Yuan Tian, Xueyong Zhu, and Rongxin Sun

Abstract

We construct new randomized algorithms to find the exact solution to the shortest and closest vector problems (SVP and CVP) in Euclidean norm (l2) for the integral lattice. Not only the minimal norm of non-zero lattice vectors in SVP and the minimal distance in CVP, but also how many lattice vectors reach those minimums can be simultaneously computed by the algorithms. Our approach is based on some special properties of the generating function of lattice vectors’ (l2-)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 h=l(Λn) (the minimal positive integer such that the dual lattice Λn* scaled by h1/2 is integral) polynomial in n, the case frequently occurring in applications, this algorithm can find the minimal l2-norm of non-zero lattice vectors and the number of such shortest vectors in Λn with success probability 1-ε in asymptotic space complexity of polynomial in n and asymptotic time complexity of nO(n)log(1/ε). The only contribution to the algorithm’s exponential time complexity nO(n)log(1/ε) comes from independently repeating a randomized lattice vector sampler nO(n)log(1/ε) 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. In other words, our solvers can be easily parallelized to be polynomial in time complexity. In addition, a variant of our CVP solver can solve the closest vector problem with preprocessing (CVPP) in polynomial time and nO(n)log(1/ε) space complexity.