Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR06-148 | 15th February 2007 00:00

Limits on the Hardness of Lattice Problems in $ell_p$ Norms Revision of: TR06-148

RSS-Feed




Revision #1
Authors: Chris Peikert
Accepted on: 15th February 2007 00:00
Downloads: 2675
Keywords: 


Abstract:


We show that several recent ``positive'' results for lattice
problems in the $\ell_2$ norm also hold in $\ell_p$ norms, for any
$p > 2$. In particular, for lattices of dimension $n$:

* Approximating the shortest and closest vector in the $\ell_p$
norm to within $\tilde{O}(\sqrt{n})$ factors is contained in
$\coNP$.

* Approximating the length of the shortest vector in the
$\ell_p$ norm to within $\tilde{O}(n)$ factors reduces to the
average-case problems studied in related works (Ajtai, STOC
1996; Micciancio and Regev, FOCS 2004; Regev, STOC 2005).

These results improve upon the current understanding of $\ell_p$
norms by up to a $\sqrt{n}$ factor. Taken together, they can be
viewed as a partial converse to recent reductions from the $\ell_2$
norm to $\ell_p$ norms (Regev and Rosen, STOC 2006).

One of our main technical contributions is a very general analysis
of Gaussian distributions over lattices, which may be of independent
interest. Our proofs employ analytical techniques of Banaszczyk
which, to our knowledge, have yet to be exploited in computer
science.


Paper:

TR06-148 | 4th December 2006 00:00

Limits on the Hardness of Lattice Problems in $\ell_p$ Norms





TR06-148
Authors: Chris Peikert
Publication: 6th December 2006 19:01
Downloads: 2000
Keywords: 


Abstract:

We show that for any $p \geq 2$, lattice problems in the $\ell_p$
norm are subject to all the same limits on hardness as are known
for the $\ell_2$ norm. In particular, for lattices of dimension
$n$:

* Approximating the shortest and closest vector in the
$\ell_p$ norm to within $\tilde{O}(\sqrt{n})$ factors is
contained in $\coNP$.

* Approximating the length of the shortest vector in the
$\ell_p$ norm to within $\tilde{O}(n)$ factors reduces to the
same average-case problems that have been studied in related
works (Ajtai, STOC 1996; Micciancio and Regev, FOCS 2004; Regev,
STOC 2005).

Each of these results improves upon the current understanding of
$\ell_p$ norms by up to a $\sqrt{n}$ factor. Taken together, they
can be seen as a partial converse to recent reductions from
lattice problems in the $\ell_2$ norm to corresponding problems in
$\ell_p$ norms (Regev and Rosen, STOC 2006).

One of our main technical contributions is a general analysis of
\emph{sums} of independent Gaussian distributions over lattices,
which may be of independent interest. Our proofs employ
analytical techniques of Banaszczyk which, to our knowledge, have
yet to be exploited in computer science.



ISSN 1433-8092 | Imprint