OT-Combiners via Secure Computation

An

OT-combiner

implements a secure oblivious transfer (OT) protocol using oracle access to

n

OT-candidates of which at most

t

may be faulty. We introduce a new general approach for combining OTs by making a simple and modular use of protocols for secure computation. Specifically, we obtain an OT-combiner from any instantiation of the following two ingredients: (1) a

t

-secure

n

-party protocol for the OT functionality, in a network consisting of secure point-to-point channels and a broadcast primitive; and (2) a secure two-party protocol for a functionality determined by the former multiparty protocol, in a network consisting of a single OT-channel. Our approach applies both to the “semi-honest” and the “malicious” models of secure computation, yielding the corresponding types of OT-combiners.

Instantiating our general approach with secure computation protocols from the literature, we conceptually simplify, strengthen the security, and improve the efficiency of previous OT-combiners. In particular, we obtain the first

constant-rate

OT-combiners in which the number of secure OTs being produced is a constant fraction of the total number of calls to the OT-candidates, while still tolerating a constant fraction of faulty candidates (

t

 = 

Ω

(

n

)). Previous OT-combiners required either

ω

(

n

) or poly(

k

) calls to the

n

candidates, where

k

is a security parameter, and produced only a single secure OT.

We demonstrate the usefulness of the latter result by presenting several applications that are of independent interest. These include:

Constant-rate OTs from a noisy channel.

We implement

n

instances of a standard

${2\choose 1}$

-OT by communicating just

O

(

n

) bits over a noisy channel (binary symmetric channel). Our reduction provides unconditional security in the semi-honest model. Previous reductions of this type required the use of

Ω

(

kn

) noisy bits.

Better amortized generation of OTs.

We show that, following an initial “seed” of

O

(

k

) OTs, each additional OT can be generated by only computing and communicating a

constant

number of outputs of a cryptographic hash function. This improves over a protocol of Ishai

et al.

(Crypto 2003), which obtained similar efficiency in the semi-honest model but required

Ω

(

k

) applications of the hash function for generating each OT in the malicious model.