Craig Gentry, Chris Peikert, Vinod Vaikuntanathan

We show how to construct a variety of ``trapdoor'' cryptographic tools

assuming the worst-case hardness of standard lattice problems (such as

approximating the shortest nonzero vector to within small factors).

The applications include trapdoor functions with \emph{preimage

sampling}, simple and efficient ``hash-and-sign'' digital signature

schemes, universally composable oblivious transfer, ...
more >>>

Chris Peikert

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 ...
more >>>

Sanjeev Arora, Rong Ge

In the {\em learning parities with noise} problem ---well-studied in learning theory and cryptography--- we

have access to an oracle that, each time we press a button,

returns a random vector $ a \in \GF(2)^n$ together with a bit $b \in \GF(2)$ that was computed as

$a\cdot u +\eta$, where ...
more >>>