Constant-Rate Oblivious Transfer from Noisy Channels

A

binary symmetric channel

(BSC) is a noisy communication channel that flips each bit independently with some fixed error probability 0 < 

p

 < 1/2. Crépeau and Kilian (FOCS 1988) showed that oblivious transfer, and hence general secure two-party computation, can be

unconditionally

realized by communicating over a BSC. There has been a long line of works on improving the efficiency and generality of this construction. However, all known constructions that achieve security against

malicious

parties require the parties to communicate

poly(k)

bits over the channel for each instance of oblivious transfer (more precisely,

${2\choose 1}$

-

bit

-OT) being realized, where

k

is a statistical security parameter. The question of achieving a constant (positive) rate was left open, even in the easier case of realizing a single oblivious transfer of a long string.

We settle this question in the affirmative by showing how to realize

n

independent instances of oblivious transfer, with statistical error that vanishes with

n

, by communicating just

O

(

n

) bits over a BSC. As a corollary, any boolean circuit of size

s

can be securely evaluated by two parties with

O

(

s

) + 

poly

(

k

) bits of communication over a BSC, improving over the

O

(

s

)·

poly

(

k

) complexity of previous constructions.