On the Cryptographic Complexity of the Worst Functions

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

]×[

N

] → {0,1} can be securely evaluated using

$\tilde{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

 ⊆ [

N

]×[

N

].

Correlated randomness complexity of secure two-party computation.

Every function

f

:[

N

]×[

N

] → {0,1} can be securely evaluated using

$2^{\tilde{O}{\sqrt{\log N}}}$

bits of correlated randomness.

Communication complexity of private simultaneous messages.

Every function

f

:[

N

]×[

N

] → {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

$\tilde{O}{\sqrt{N}}$

.

The worst-case complexity of the best previous solutions was Ω(

N

) for the first three problems and Ω(

N

/log

N

) for the last one. 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.