Oblivious Transfer (OT)

What is OT?

In cryptography, an Oblivious Transfer (OT) protocol is a type of protocol in which a sender transfers one of potentially many pieces of information to a receiver, but remains oblivious as to what piece (if any) has been transferred.

Rabin OT

The first form of oblivious transfer was introduced in 1981 by Michael O. Rabin. Rabin oblivious transfer is a kind of formalization of "noisy wire" communication. The objective is to simulate a random loss of information. Formally, a Rabin OT machine models the following behavior:

• The sender $S$ sends a bit $b$ into the OT machine.

• The machine then flips a coin, and with probability $\frac{1}{2}$ sends $b$ to the receiver $R$, and with probability $\frac{1}{2}$ sends # to $R$ to signify that a bit was sent, but the information was lost in the transfer.

• The result is, $R$ received either $b$ or # but S does not know which output $R$ received.

Note that this may be simulated by a sufficiently noisy wire, provided that the wire transmits faithfully a good proportion of bits and at the same time loses a good proportion of bits, replacing them with noise that is distinguishable from information.

Rabin Oblivious Transfer

1-2 OT

Even, Goldreich and Lempel formulated a notion of oblivious transfer that has proven useful in various applications. In this situation:

• $S$ sends an ordered pair of bits $(b_0, b_1)$ into the 1-2-OT machine.

• $R$ then gives the machine a bit $i$, indicating which input he would like to receive.

• The machine outputs the selected bit $b_i$ and discards the other bit $b_{1-i}$.

• $S$ knows that $R$ has one of the bits, but not which one.

1-2 OT

Rabin OT == 1-2 OT

Theoretically, Rabin OT and 1-2 OT are equivalently. That is, given a black-box Rabin OT we can implement 1-2 OT, and vice versa.

Reference

http://web.cs.ucla.edu/~rafail/PUBLIC/OstrovskyDraftLecNotes2010.pdf