## Extending Oblivious Transfers Efficiently

*Yuval Ishai, Joe Kilian, Kobbi Nissim, Erez Petrank*

CRYPTO 2003 [pdf] [bibtex]

Introduces the concept of **OT extension**. It is well known that oblivious transfer (OT) cannot be based on symmetric-key primitives alone (in a black-box way). Hence OT protocols necessarily rely on expensive public-key operations. OT extension is a method for obtaining a large number of effective OTs using only a small number of "base" OTs (depending only on the security parameter) plus symmetric-key operations, minimizing the cost of OT in an amortized sense.

The protocol achieves `⚠ {$n$}`

instances of 1-out-of-2, `⚠ {$\ell$}`

-bit string OT, using only `⚠ {$k$}`

instances of 1-out-of-2, `⚠ {$n$}`

-bit string OT, where `⚠ {$k$}`

is the security parameter. Note that it is trivial to extend the *bit length* of an OT by transfering (via a base OT) a length-`⚠ {$k$}`

seed to a PRG and masking a longer message with the PRG output (this variant of OT extension is due to Beaver). Hence, the important parameter is that a small, fixed number `⚠ {$k$}`

of OTs is extended to an arbitrarily larger number `⚠ {$n$}`

of OTs.

- The receiver chooses a random
`⚠ {$n \times k$}`

matrix`⚠ {$T$}`

of bits and a string`⚠ {$r \in \{0,1\}^n$}`

denoting his choice bits in the`⚠ {$n$}`

logical OTs. The sender chooses random string`⚠ {$s \in \{0,1\}^k$}`

. - Let
`⚠ {$T_{*,j}$}`

denote the`⚠ {$j$}`

th column of`⚠ {$T$}`

(an`⚠ {$n$}`

-bit string). The parties use the base OTs (in the opposite direction!), with the receiver providing messages`⚠ {$T_{*,j}$}`

and`⚠ {$T_{*,j} \oplus r$}`

, and the sender providing choice bit`⚠ {$s_j$}`

. - Let
`⚠ {$Q$}`

denote the matrix that the sender receives from these base OTs (received*column-wise*). Let`⚠ {$Q_{i,*}$}`

denote the`⚠ {$i$}`

th*row*of`⚠ {$Q$}`

. The important part of the protocol is that`⚠ {$Q_{i,*}$}`

is either`⚠ {$T_{i,*}$}`

or`⚠ {$T_{i,*} \oplus s$}`

, depending on the receiver's choice bit`⚠ {$r_i$}`

. - To execute the
`⚠ {$i$}`

th logical OT, the sender encrypts the two messages`⚠ {$m_0, m_1$}`

under one-time pads with keys`⚠ {$H(i \| Q_{i,*})$}`

and`⚠ {$H(i \| Q_{i,*} \oplus s)$}`

, respectively, where`⚠ {$H$}`

is a random oracle. Exactly one of these masks is`⚠ {$H(i\|T_{i,*})$}`

, according to the receiver's choice bit, so the receiver can unmask his desired message. The other mask is`⚠ {$H(i\| T_{i,*} \oplus s)$}`

, where`⚠ {$s$}`

is unknown to the receiver.

Note that, besides the base OTs, the only other operations are calls to the random oracle `⚠ {$H$}`

. The protocol is secure against semi-honest adversaries. A cut-and-choose technique can be used to provide security in the malicious setting.

For simplicity, the hash function `⚠ {$H$}`

is assumed to be a random oracle. More concretely, the protocol requires that the joint distribution of

`⚠ {$t_1,t_2,...,t_n$}`

and `⚠ {$H(1\|t_1\oplus s),H(2\|t_2\oplus s),...,H(n\|t_n\oplus s) $}`

be psuedorandom where `⚠ {$s$}`

is unknown. This security property is called **correlation-robustness.**

### Other links:

### Categories:

- Home page
- All papers, by:
- .. category
- .. author names
- .. publication date
- .. recently added
- .. recently updated

- Glossary
- About
- Just getting started in MPC?
- Guidelines
- Todo List

Search Papers

Bibliography Categories