Paper 2013/594

A Local-Global Approach to Solving Ideal Lattice Problems

Yuan Tian, Rongxin Sun, and Xueyong Zhu

Abstract

We construct an innovative SVP(CVP) solver for ideal lattices in case of any relative extension of number fields L/K of degree n where L is real(contained in R). The solver, by exploiting the relationships between the so-called local and global number fields, reduces solving SVP(CVP) of the input ideal A in field L to solving a set of (at most n) SVP(CVP) of the ideals Ai in field Li with relative degree 1&#8804;ni<n and &#8721;ini=n, and the solution to the original problem can be efficiently reconstructed from the solutions to the sub-problems. The solver’s space-complexity is polynomial and its time-complexity’s explicit dependence on the dimension (relative extension degree n) is also polynomial. More precisely, our solver’s time-complexity is poly(n,|S|, NPG, NPT, Nd, Nl) where |S| is bit-size of the input data and NPG, NPT, Nd, Nl are the number of calls to some oracles for some relatively simpler problems (some of which are decisional). This feature implies that if such oracles can be implemented by efficient algorithms (with time-complexity polynomial in n), which is really possible in some situations, our solver will perform in this case with time-complexity polynomial in n. Even there is no efficient implementations for these oracles, this solver’s time-complexity may still be significantly lower than those for general lattices.