We show that any 1-round 2-server Private Information
Retrieval Protocol where the answers are 1-bit long must ask questions
that are at least $n-2$ bits long, which is nearly equal to the known
$n-1$ upper bound. This improves upon the approximately $0.25n$ lower
bound of Kerenidis and de Wolf while ... more >>>

Secure computation is one of the most fundamental cryptographic tasks.
It is known that all functions can be computed securely in the
information theoretic setting, given access to a black box for some
complete function such as AND. However, without such a black box, not
all functions can be securely ... more >>>

We study the problem of non-interactive correlation distillation
(NICD). Suppose Alice and Bob each has a string, denoted by
$A=a_0a_1\cdots a_{n-1}$ and $B=b_0b_1\cdots b_{n-1}$,
respectively. Furthermore, for every $k=0,1,...,n-1$, $(a_k,b_k)$ is
independently drawn from a distribution $\noise$, known as the ``noise
mode''. Alice and Bob wish to ``distill'' the correlation
more >>>