Paper 2006/444

Lattices that Admit Logarithmic Worst-Case to Average-Case Connection Factors

Chris Peikert and Alon Rosen

Abstract

We demonstrate an \emph{average-case} problem which is as hard as finding $\gamma(n)$-approximate shortest vectors in certain $n$-dimensional lattices in the \emph{worst case}, where $\gamma(n) = O(\sqrt{\log n})$. The previously best known factor for any class of lattices was $\gamma(n) = \tilde{O}(n)$. To obtain our results, we focus on families of lattices having special algebraic structure. Specifically, we consider lattices that correspond to \emph{ideals} in the ring of integers of an algebraic number field. The worst-case assumption we rely on is that in some $\ell_p$ length, it is hard to find approximate shortest vectors in these lattices, under an appropriate form of preprocessing of the number field. Our results build upon prior works by Micciancio (FOCS 2002), Peikert and Rosen (TCC 2006), and Lyubashevsky and Micciancio (ICALP 2006). For the connection factors $\gamma(n)$ we achieve, the corresponding \emph{decisional} promise problems on ideal lattices are \emph{not} known to be NP-hard; in fact, they are in P. However, the \emph{search} approximation problems still appear to be very hard. Indeed, ideal lattices are well-studied objects in computational number theory, and the best known algorithms for them seem to perform \emph{no better} than the best known algorithms for general lattices. To obtain the best possible connection factor, we instantiate our constructions with infinite families of number fields having constant \emph{root discriminant}. Such families are known to exist and are computable, though no efficient construction is yet known. Our work motivates the search for such constructions. Even constructions of number fields having root discriminant up to $O(n^{2/3-\epsilon})$ would yield connection factors better than the current best of~$\tilde{O}(n)$.

Metadata
Available format(s)
PDF PS
Category
Foundations
Publication info
Published elsewhere. Unknown where it was published
Keywords
latticesworst-case to average-case reductionsnumber fields
Contact author(s)
cpeikert @ alum mit edu
History
2006-12-04: received
Short URL
https://ia.cr/2006/444
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2006/444,
      author = {Chris Peikert and Alon Rosen},
      title = {Lattices that Admit Logarithmic Worst-Case to Average-Case Connection Factors},
      howpublished = {Cryptology ePrint Archive, Paper 2006/444},
      year = {2006},
      note = {\url{https://eprint.iacr.org/2006/444}},
      url = {https://eprint.iacr.org/2006/444}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.