Efficient Unconditional Oblivious Transfer from Almost Any Noisy Channel

Oblivious transfer (OT)

is a cryptographic primitive of central importance, in particular in two- and multi-party computation. There exist various protocols for different variants of OT, but any such realization from scratch can be broken in principle by at least one of the two involved parties if she has sufficient computing power—and the same even holds when the parties are connected by a quantum channel. We show that, on the other hand, if

noise

—which is inherently present in any physical communication channel—is taken into account, then OT can be realized in an unconditionally secure way for both parties, i.e., even against dishonest players with unlimited computing power. We give the exact condition under which a general noisy channel allows for realizing OT and show that only “trivial” channels, for which OT is obviously impossible to achieve, have to be excluded. Moreover, our realization of OT is efficient: For a security parameter

α

> 0—an upper bound on the probability that the protocol fails in any way—the required number of uses of the noisy channel is of order

O

(

log

(1/

α

)

2 + ε

) for any

ε

> 0.