I am trying to solve this exercise.

Assume an oblivious transfer protocol that uses a trusted third party Trent.

Alice's messages $M_0$ and $M_1$ are binary values of length $k$. Bob's message selection bit is $m$.

  1. Trent -> Alice: $R_0, R_1$ where $R_0, R_1$ are random binary values each of length $k$

  2. Trent -> Bob : $t, R_t $ where $t$ is a random bit

  3. Bob -> Alice : $ b = t \oplus m$

  4. Alice -> Bob : $C_0, C_1 $

How should Alice compute $C_0$ and $C_1$? How should Bob compute $M_m$?

I guess that Alice has to compute $K_0, K_1$ as keys (probably inserted into a hash function) and then encrypt $C_0$, $C_1$ like $C_M = E_{k_m}(M_m)$. Bob then can compute $M_m$ by $M_m = D_{k_m}(C_m)$ where $K_m$ is related to $R_t$ in some way. Does anyone have an idea? Thank you

  • $\begingroup$ Hint: split it into two cases. In case Bob gets $t=m$, he sends $b=0$ which means "I got from Trent the choice that I wanted". What does this mean in terms of $R_0, R_1, R_t$? In case Bob gets $t \ne m$, he sends $b=1$ which means, "I got from Trent the opposite choice from what I wanted". What does this mean in terms of $R_0, R_1, R_t$? $\endgroup$
    – Mikero
    Dec 8, 2018 at 3:04

1 Answer 1

  1. Alice computes $C_0$ and $C_1$ as follows:

    If $b=0$ (this means $t=m$), Alice computes $$C_i = M_i \oplus R_i.$$ Otherwise (i.e. when $t=1-m$), Alice computes $$C_i = M_i \oplus R_{1-i},$$ where $i \in \{0,1\}$.

  2. Bob computes $M_m$ as $C_m\oplus R_t$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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