Recently Ajtai showed that to approximate the shortest lattice vector in the $l_2$-norm within a factor $(1+2^{-\mbox{\tiny dim}^k})$, for a sufficiently large constant $k$, is NP-hard under randomized reductions. We improve this result to show that to approximate a shortest lattice vector within a factor $(1+ \mbox{dim}^{-\epsilon})$, for any $\epsilon>0$, ... more >>>

Recently, Ajtai discovered a fascinating connection between the worst-case complexity and the average-case complexity of some well-known lattice problems. Later, Ajtai and Dwork proposed a cryptosystem inspired by Ajtai's work, provably secure if a particular lattice problem is difficult. We show that there is a converse to the Ajtai-Dwork security ... more >>>

We show that computing the approximate length of the shortest vector in a lattice within a factor c is NP-hard for randomized reductions for any constant cmore >>>

We give a method for approximating any $n$-dimensional lattice with a lattice $\Lambda$ whose factor group $\mathbb{Z}^n / \Lambda$ has $n-1$ cycles of equal length with arbitrary precision. We also show that a direct consequence of this is that the Shortest Vector Problem and the Closest Vector Problem cannot be ... more >>>

We present new faster algorithms for the exact solution of the shortest vector problem in arbitrary lattices. Our main result shows that the shortest vector in any $n$-dimensional lattice can be found in time $2^{3.199 n}$ and space $2^{1.325 n}$. This improves the best previously known algorithm by Ajtai, Kumar ... more >>>