3
$\begingroup$

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:

  1. The sender’s input consists of two m-bit strings, $x_0, x_1$.
  2. The receiver has no input.
  3. 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.

  1. It is possible to construct $RandOT^1$ from $OT^2$.
  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.

$\endgroup$
  • $\begingroup$ en.wikipedia.org/wiki/One-time_pad ​ ​ $\endgroup$ – user991 May 1 '16 at 15:45
  • $\begingroup$ I can't see how the One-Time-Pad helps here :( $\endgroup$ – Naftali Waxman May 1 '16 at 16:31
  • $\begingroup$ key length ​ = ​ message length ​ ​ ​ ​ $\endgroup$ – user991 May 1 '16 at 16:47
  • $\begingroup$ Still I don't get it... $\endgroup$ – Naftali Waxman May 1 '16 at 17:38
  • $\begingroup$ In particular, anything that can transfer a message, can instead be used to transfer a key. ​ ​ $\endgroup$ – user991 May 1 '16 at 17:42
2
$\begingroup$

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}$.

$\endgroup$
0
$\begingroup$

I just stumbled across this question and found it interesting. Since no one has posted an answer, I wanted to maybe help get the ball rolling by throwing my ideas out there. This is not an answer.

  1. Sender generates random 1-bit keys $K_0, K_1$ and inputs them into $OT^1$.
  2. Receiver reports to the sender whether or not he received the "correct" key ($K_0$ if he wants to receive message 0, $K_1$ if he wants to receive message 1).
  3. If no, go back to 1.
  4. If yes, the sender encrypts both the messages and sends the ciphertexts to the receiver. $C_i = x_i \oplus K_i$ for $i \in \{0, 1\}$.
  5. The receiver decrypts the desired message: $x_s = C_s \oplus K_s$ where $s \in \{0, 1\}$ is the receiver's selection input.

The receiver cannot learn anything about the nonselected string because $K_0$ and $K_1$ are independently selected.

There is no guarantee this algorithm will halt in a finite amount of time.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.