Welcome to the resource topic for 2008/481
Title:
Public-Key Cryptosystems from the Worst-Case Shortest Vector Problem
Authors: 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.
ePrint: https://eprint.iacr.org/2008/481
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .