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.

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