We construct public-key cryptosystems that are secure assuming the
\emph{worst-case} hardness of approximating the length of a shortest
nonzero vector in an $n$-dimensional lattice to within a small
$\poly(n)$ factor. Prior cryptosystems with worst-case connections
were based either on the shortest vector problem for a \emph{special
class} of lattices (Ajtai and Dwork, STOC 1997; Regev, J.~ACM 2004),
or on the conjectured hardness of lattice problems for \emph{quantum}
algorithms (Regev, STOC 2005).

Our main technical innovation is a reduction from certain variants of
the shortest vector problem to corresponding versions of the
``learning with errors'' ($\lwe$) problem; previously, only a
\emph{quantum} reduction of this kind was known. In addition, we
construct new cryptosystems based on the \emph{search} version of
$\lwe$, including a very natural \emph{chosen ciphertext-secure}
system that has a much simpler description and tighter underlying
worst-case approximation factor than prior constructions.