Cryptology ePrint Archive: Report 2013/412

Moduar Form Aprroach to Solving Lattice Problems

Yuan Tian, Xueyong Zhu, 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.

Category / Keywords: foundations / Lattice Problems; SVP;CVP; Modular Forms; Theta Functions

Publication Info: submitted to SoDA 2014

Date: received 22 Jun 2013

Contact author: tianyuan_ca at sina com

Available format(s): PDF | BibTeX Citation

Version: 20130625:160230 (All versions of this report)

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]