Extending Oblivious Transfers Efficiently

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.

  1. 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$}.
  2. 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$}.
  3. 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$}.
  4. 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:

Presentation slides (PPT)

Categories:

OTExtension