SPEAKER: Daniel Wichs TITLE: Public-Key Cryptosystems from the Worst-Case Shortest Vector Problem AUTHORS: Chris Peikert (Proc. of STOC 2009) ABSTRACT: 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. ONLINE VERSION: http://people.csail.mit.edu/cpeikert/pubs/svpcrypto.pdf