Revision #1 Authors: Chris Peikert, Alon Rosen

Accepted on: 4th April 2007 00:00

Downloads: 2713

Keywords:

We demonstrate an \emph{average-case} problem that 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

non-trivial class of lattices was $\gamma(n) = \tilde{O}(n)$.

Our results apply to 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 problem we rely on is to find approximate shortest

vectors in these lattices, under an appropriate form of

preprocessing of the number field.

For the connection factors $\gamma(n)$ we achieve, the corresponding

\emph{decision} 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~$\tilde{O}(n)$.

As an additional contribution, we give reductions between various

worst-case problems on ideal lattices, showing for example that the

shortest vector problem is no harder than the closest vector

problem. These results are analogous to previously-known reductions

for general lattices.

TR06-147 Authors: Chris Peikert, Alon Rosen

Publication: 6th December 2006 18:57

Downloads: 3264

Keywords:

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)$.