1-out-of-2 OT from Random 1-out-of-2 OT Last week I came upon this problem in my h.w.:


  Let $OT^m$ denote 1-out-of-2 oblivious transfer of $m$ bit inputs.
  
  Let $RandOT^m$ denote the following primitive:
  
  
  The sender’s input consists of two m-bit strings, $x_0, x_1$.
  The receiver has no input.
  At the end of the protocol the receiver learns $(b,x_b)$, for a randomly chosen $b$ in $\{0,1\}$, and learns nothing about $x_{1-b}$. The sender learns nothing. (Note that $b$ must be chosen at random, and neither nor the server should be able to choose the value of $b$).
  
  
  Show the following two reductions, for the semi-honest case.
  
  
  It is possible to construct $RandOT^1$ from $OT^2$.
  It is possible to construct $OT^1$ from $RandOT^1$.
  


I solved the first problem quite easily, but I just can't figure a way to solve the second one.
We construct $OT^1$ from $RandOT^1$ as follows. Say, the Sender (S) has messages $m_0, m_1$ and the Receiver (R) has choice bit $c$. I.e., R needs to learn $m_c$. Now we first run the random OT. S now has random $x_0, x_1$ and R has $x_b,b$. The idea is now for S to somehow OTP $m_c$ with $x_b$ and $m_{c \oplus 1}$ with $x_{b \oplus 1}$ and send these values to R.

To do this R sends $d = b \oplus c$ to S (note this hides c as a OTP). S then sends $(y_0, y_1) = (x_{d} \oplus m_0, x_{d \oplus 1} \oplus m_1)$ to R. Note that we can write $y_i = x_{d \oplus i} \oplus m_i$. R then finds $m_c = y_c \oplus x_b$. Note, $y_c = y_{d \oplus b} = x_{d \oplus d \oplus b} \oplus m_c = x_b \oplus m_c$, thus we get the correct result. Also note, R does not learn $m_{c \oplus 1}$ as it is OTP'ed with $x_{b \oplus 1}$.