ECCC-Report TR08-100https://eccc.weizmann.ac.il/report/2008/100Comments and Revisions published for TR08-100en-usThu, 20 Nov 2008 15:47:42 +0200
Paper TR08-100
| Public-Key Cryptosystems from the Worst-Case Shortest Vector Problem |
Chris Peikert
https://eccc.weizmann.ac.il/report/2008/100We 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.
Thu, 20 Nov 2008 15:47:42 +0200https://eccc.weizmann.ac.il/report/2008/100