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

Abstract

We construct public-key cryptosystems that are secure assuming the
*worst-case* hardness of approximating the shortest vector problem on
lattices.  Prior cryptosystems with worst-case connections (e.g., the
Ajtai-Dwork system) were based either on a *special case* of the
shortest vector problem, or on the conjectured hardness of lattice
problems for *quantum* algorithms.

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 quantum reduction of
this kind was known.  In addition, we construct new cryptosystems
based on LWE, including a very natural chosen ciphertext-secure system
that has a much simpler description and tighter underlying worst-case
approximation factor than prior constructions.

(Duration: 30 minutes, on or before Wednesday.)