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