Abstract |
We study the complexity of realizing the "worst" functions in several
standard models of information-theoretic cryptography. In particular,
for the case of security against passive adversaries, we obtain the
following main results.
- OT complexity of secure two-party computation: Every function
$f:[N]\times [N]\to\{0,1\}$ can be securely evaluated using
$\softO{N^{2/3}}$ invocations of an oblivious transfer oracle. A
similar result holds for securely sampling a uniform pair of outputs
from a set $S\subseteq [N]\times [N]$.
- Correlated randomness complexity of secure two-party computation:
Every function $f:[N]\times [N]\to\{0,1\}$ can be securely evaluated
using $2^{\softO{\sqrt{\log N}}}$ bits of correlated randomness.
- Communication complexity of private simultaneous messages: Every
function $f:[N]\times [N]\to\{0,1\}$ can be securely evaluated in the
non-interactive model of Feige, Kilian, and Naor (STOC 1994) with
messages of length $O(\sqrt{N})$.
- Share complexity of forbidden graph access structures: For every
graph $G$ on $N$ nodes, there is a secret-sharing scheme for $N$
parties in which each pair of parties can reconstruct the secret if
and only if the corresponding nodes in $G$ are connected, and where
each party gets a share of size $\softO{\sqrt{N}}$.
For all of these problems, the worst-case complexity of the best
previous solutions was $\Omega(N/\log N)$.
The above results are obtained by applying general transformations to
variants of private information retrieval (PIR) protocols from the
literature, where different flavors of PIR are required for different
applications.
This is joint work with Amos Beimel (BGU), Yuval Ishai (Technion),
Eyal Kushilevitz (Technion).
|