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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
shortest lattice vector problemsclosest lattice vector problemsideal latticesfield valuationsnon-Archimedean valuationslocal fieldglobal field.
Contact author(s)
tianyuan_ca @ sina com
History
2013-09-14: received
Short URL
https://ia.cr/2013/594
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2013/594,
      author = {Yuan Tian and Rongxin Sun and Xueyong Zhu},
      title = {A Local-Global Approach to Solving Ideal Lattice Problems},
      howpublished = {Cryptology ePrint Archive, Paper 2013/594},
      year = {2013},
      note = {\url{https://eprint.iacr.org/2013/594}},
      url = {https://eprint.iacr.org/2013/594}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.