Daniel Wichs

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

Chris Peikert (Proc. of STOC 2009)

We construct public-key cryptosystems that are secure assuming the
worst-case hardness of approximating the minimum distance on
n-dimensional lattices to within small poly(n) factors. Prior
cryptosystems with worst-case connections were based either on the
shortest vector problem for a special class of lattices (Ajtai and
Dwork, STOC 1997; Regev, J. ACM 2004), or on the conjectured hardness of
lattice problems for quantum algorithms (Regev, STOC 2005).

Our main technical innovation is a reduction from variants of the
shortest vector problem to corresponding versions of the “learning with
errors” (LWE) problem; previously, only a quantum reduction of this kind
was known. As an additional contribution, we construct a natural chosen
ciphertext-secure cryptosystem having a much simpler description and
tighter underlying worst-case approximation factor than prior schemes.