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.
Category / Keywords: foundations / Lattice-based cryptography, learning with errors, quantum computation Date: received 13 Nov 2008 Contact author: cpeikert at alum mit edu Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation Version: 20081119:041110 (All versions of this report) Short URL: ia.cr/2008/481