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

Jonathan Ullman, Salil Vadhan

Assuming the existence of one-way functions, we show that there is no

polynomial-time, differentially private algorithm $A$ that takes a database

$D\in (\{0,1\}^d)^n$ and outputs a ``synthetic database'' $\hat{D}$ all of whose two-way

marginals are approximately equal to those of $D$. (A two-way marginal is the fraction

of database rows ...
more >>>