Most cryptographic primitives require randomness (for example, to generate their secret keys). Usually, one assumes that perfect randomness is available, but, conceivably, such primitives might be built under weaker, more realistic assumptions. This is known to be true for many authentication applications, when entropy alone is typically sufficient. In contrast, ... more >>>

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

We introduce a new combinatorial object, called a \emph{design extractor}, that has both the properties of a design and an extractor. We give efficient constructions of such objects and show that they can be used in several applications.

\begin{enumerate}
\item {Improving the output length of known non-malleable extractors.} Non-malleable extractors ... more >>>

Dodis and Wichs \cite{DW09} introduced the notion of a non-malleable extractor to study the problem of privacy amplification with an active adversary. A non-malleable extractor is a much stronger version of a strong extractor. Given a weakly-random string $x$ and a uniformly random seed $y$ as the inputs, the non-malleable ... more >>>