## Constant-Rate Oblivious Transfer from Noisy Channels

**Yuval Ishai** (1),
**Eyal Kushilevitz** (1),
**Rafail Ostrovsky** (2),
**Manoj Prabhakaran** (3),
**Amit Sahai** (2), and
**Jürg Wullschleger** (4)

(1) * Technion, Haifa, Israel*

(2) *University of California, Los Angeles, USA*

(3) *University of Illinois, Urbana-Champaign, USA*

(4) *Université of Montréal and McGill University, Canada*

**Abstract.**
A *binary symmetric channel* (BSC) is a noisy communication
channel that ips 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.