How Many Oblivious Transfers Are Needed for Secure Multiparty Computation?

Oblivious transfer (OT) is an essential building block for secure multiparty computation when there is no honest majority. In this setting, current protocols for

n

 ≥ 3 parties require

each pair of parties

to engage in a single OT for

each gate

in the circuit being evaluated. Since implementing OT typically requires expensive public-key operations (alternatively, expensive setup or physical infrastructure), minimizing the number of OTs is a highly desirable goal.

In this work we initiate a study of this problem in both an information-theoretic and a computational setting and obtain the following results.

If the adversary can corrupt up to

t

 = (1 − 

ε

)

n

parties, where

ε

> 0 is an arbitrarily small constant, then a total of

O

(

n

) OT channels between pairs of parties are necessary and sufficient for general secure computation. Combined with previous protocols for “extending OTs”,

O

(

nk

) invocations of OT are sufficient for computing arbitrary functions with computational security, where

k

is a security parameter.

The above result does not improve over the previous state of the art in the important case where

t

 = 

n

 − 1, when the number of parties is small, or in the information-theoretic setting. For these cases, we show that an arbitrary function

f

:{0,1}

n

→{0,1}

*

can be securely computed by a protocol which makes use of a single OT (of strings) between each pair of parties. This result is tight in the sense that at least one OT between each pair of parties is necessary in these cases. A major disadvantage of this protocol is that its communication complexity grows exponentially with

n

. We present natural classes of functions

f

for which this exponential overhead can be avoided.