Public-Key Cryptosystems from the Worst-Case Shortest Vector Problem

Chris Peikert

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'' () 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 , 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 cryptography learning with errors quantum 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},
      url = {https://eprint.iacr.org/2008/481}
}