Theory Seminar: On the Cryptographic Complexity of the Worst Functions
 Speaker:
 Ranjit Kumaresan (CS, Technion)
 Date:
 Wednesday, 22.1.2014, 12:30
 Place:
 Taub 201
We study the complexity of realizing the "worst" functions in several standard models of informationtheoretic cryptography. In particular, for the case of security against passive adversaries, we obtain the following main results.

OT complexity of secure twoparty computation: Every function $f:[N]\times [N]\to\{0,1\}$ can be securely evaluated using $O({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 twoparty computation: Every function $f:[N]\times [N]\to\{0,1\}$ can be securely evaluated using $2^{O({\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 noninteractive 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 secretsharing 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 $O({\sqrt{N}})$.
For all of these problems, the worstcase 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).