Welcome to the resource topic for 2013/594
Title:
A Local-Global Approach to Solving Ideal Lattice Problems
Authors: Yuan Tian, Rongxin Sun, 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≤ni<n and ∑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.
ePrint: https://eprint.iacr.org/2013/594
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .