Paper 2008/481
Public-Key Cryptosystems from the Worst-Case Shortest Vector Problem
Chris Peikert
Abstract
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.
Metadata
- Available format(s)
-
PDF
PS
- Category
- Foundations
- Publication info
- Published elsewhere. Unknown where it was published
- Keywords
- Lattice-based cryptographylearning with errorsquantum computation
- Contact author(s)
- cpeikert @ alum mit edu
- History
- 2008-11-19: received
- Short URL
- https://ia.cr/2008/481
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2008/481,
author = {Chris Peikert},
title = {Public-Key Cryptosystems from the Worst-Case Shortest Vector Problem},
howpublished = {Cryptology ePrint Archive, Paper 2008/481},
year = {2008},
note = {\url{https://eprint.iacr.org/2008/481}},
url = {https://eprint.iacr.org/2008/481}
}
