Public-Key Cryptosystems from the Worst-Case Shortest Vector Problem
Speaker: Chris Peikert , SRI International
Date: November 21 2008
Time: 10:30AM to 12:00PM
Location: 32-G449 (Kiva), Stata Center, 32 Vassar Street
Contact: be, 3-6098, imbe
Relevant URL:
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.
See other events that are part of CIS/Microsoft Seminars 2008/2009
See other events happening in November 2008
