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