eprint.iacr.org/2008/481
Preview meta tags from the eprint.iacr.org website.
Linked Hostnames
4Thumbnail
Search Engine Appearance
Public-Key Cryptosystems from the Worst-Case Shortest Vector Problem
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.
Bing
Public-Key Cryptosystems from the Worst-Case Shortest Vector Problem
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.
DuckDuckGo
Public-Key Cryptosystems from the Worst-Case Shortest Vector Problem
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.
General Meta Tags
14- titlePublic-Key Cryptosystems from the Worst-Case Shortest Vector Problem
- charsetutf-8
- viewportwidth=device-width, initial-scale=1, shrink-to-fit=no
- citation_titlePublic-Key Cryptosystems from the Worst-Case Shortest Vector Problem
- citation_authorChris Peikert
Open Graph Meta Tags
7- og:imagehttps://eprint.iacr.org/img/iacrlogo.png
- og:image:altIACR logo
- og:urlhttps://eprint.iacr.org/2008/481
- og:site_nameIACR Cryptology ePrint Archive
- og:typearticle
Link Tags
2- stylesheet/css/dist/css/bootstrap.min.css
- stylesheet/css/eprint.css?v=10
Links
27- https://creativecommons.org/licenses/by/4.0
- https://eprint.iacr.org
- https://eprint.iacr.org/2008/481.pdf
- https://eprint.iacr.org/2008/481.ps
- https://eprint.iacr.org/about.html