2  Oblivious Transfer

2.1 What is Oblivious Transfer?

If you’re not familiar with Boolean operation XOR, please reference the following truth table:

\begin{array}{ccc} A & B & A \oplus B \\ 0 & 0 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 1 \\ 1 & 1 & 0 \end{array}

In standard computing practice, we often run into the issue of wanting to transfer values between parties. This problem can be modeled as follows:

Suppose that Alice has a set of values \{s_{1},s_{2},\dots,s_{n}\} and Bob holds a selection bit i. Bob would like to obtain the value of s_{i} from Alice.

Without accounting for security, this can easily be accomplished by Bob sending his selection bit to Alice, and Alice sending the corresponding value s_{i} to Bob or Alice sending her entire set of values to Bob, and Bob picking the desired value s_{i} from the obtained set.

However, in Secure MPC (multi-party computation) we are concerned with the security of this process. More specifically, it is important that Bob doesn’t learn anything about Alice’s s_{i}\text{'s} other than the one he receives and Alice doesn’t learn anything about Bob’s selection bit i. Oblivious transfer is the secure mechanism by which we achieve this outcome. This is an extremely important Secure MPC tool because it has been proven that OT is complete for all Secure MPC operations (see O. Golrich (1987) and Killian (1988)).

As such, OT forms the basis for many secure computation protocols which have been developed in the past 40 years or so.

2.2 Extending Oblivious Transfer

Due to the the time complexity associated with Oblivious Transfer, researchers have been motivated to search for efficiency gains. Towards this end, several important developments have been made over time:

  • It was demonstrated by R. Impagliazzo (1989) that if a reduction of OT to one-way-functions (black-box reduction) could be performed, it would imply that P \ne NP (polynomial-class algorithm problems and NP class problems are not complexity-equivalent)
    • in other words, OT is harder than one-way-functions which form the basis of symmetric key encryption. See Chapter 3 for more information on this (OWF) one-way-functions.
  • Beaver demonstrated one could extend a series of small base OT’s to a large number of OT’s using ONLY OWF’s Beaver (1996)
  • IKNP OT - (proposed in Y. Ishai (2003))
    • uses ROM (random oracle model) and symmetric key primitives to increase security and improve efficiency of OT
  • Silent OT (Ferret) - (proposed in K. Yang (2020))
  • Exponential Correlated OTs based on LPN Assumption (proposed in E. Boyle (2020))

2.3 Fundamentals of Oblivious Transfer

2.3.1 Random Oblivious Transfer (ROT)

what is the difference between ROT_{l}^{m} and OT_{l}^{m}?

Random Oblivious Transfer is the most general form of OT. In this setting, we assume that there are two parties involved: Alice and Bob. Here, Alice functions as the sender and Bob functions as the receiver. Additionally, we assume a 1-out-of-2 ROT functionality. Alice and Bob follow the ROT_{m}^{l} protocol below:

The receiver (Bob) provides its selection bit b to the protocol, and two random strings are generated by the ROT protcol. These are r_{0} and r_{1}, one of which corresponds to the input bit b. The protocol provides these two random strings to the sender, and provides the receiver with a bit r_{b} \in \{r_{0},r_{1}\} which corresponds to the receiver’s selection bit*.

How are bits selected by the protocol without assistance of a TTP?

Case 1: Bob uses the same selection bit b

Once the random outputs have been generated for Alice and Bob, they collectively perform an instance of {2 \choose 1}\text{-OT}.

  1. Alice inputs chosen bits (x_{0}, x_{1}) and Bob inputs selection bit b
  2. Alice sends to Bob (x_{0} \oplus r_{0}, x_{1} \oplus r_{1})
  3. Bob performs (x_{b} \oplus r_{b}) \oplus r_{b} to obtain x_{b}

Here, only one message is passed from Alice to Bob S \rightarrow R

Case 2: Bob chooses a different selection bit c

  1. Bob sends to Alice k = b \oplus c where b was the chosen bit input to the ROT protocol, and c is the chosen bit of the {2\choose 1}\text{-OT}
  2. Alice permutes k with r_{0} and r_{1} to get r_{k} and r_{\overline{k}}.
  3. Alice sends (y_{0}, y_{1}) = (x_{0} \oplus r_{k}, x_{1} \oplus r_{\overline{k}}) to Bob
  4. Bob performs y_{c} \oplus r_{b} to obtain x_{c}

2.3.2 Correlated Oblivious Transfer (COT)

Correlated Oblivious transfer has functionality defined as follows:

  • The sender (Alice) has values x_{0}, x_{1} such that the \oplus of these values together results in \delta
  • Alice inputs \Delta and receives r (a random l-bit string) and r\oplus \Delta.
  • The receiver (Bob) obtains r\oplus b \Delta.

We use the notation COT_{k}^{m} to represent the correlated oblivious tranfer functionality. Here m is the number of OT’s to perform, and k is length of the random bit-strings used to mask the values exchanged.

In this setting, the ROT_{l}^{m} problem can be reduced to COT_{k}^{m}. If a random oracle is given, we can hash the output of a k length output to an l length output for ROT_{l}^{m}. However, it is not strictly necessary to use a random oracle. A correlation robust hash function may be used given that the joint distribution of hashes (h(t_{1} \oplus s),h(t_{2}\oplus s),\dots h(t_{m}\oplus s)) for strings s, t_{1},\dots, t_{m} given t_{1},\dots,t_{m} is pseudo-random.

2.3.3 IKNP