5
$\begingroup$

If we define Oblivious Transfer as following:

Alice inputs $(x_0,x_1) \in F^2$, where $F$ is a field, and Bob inputs $b\in\{0,1\}$, then Alice gets a dummy output(for which she knows nothing about b), and Bob gets $x_b$. Now if we use a Random functionality R, which requires no input but output random bits $(z_0,z_1)\in F^2$ to Alice and $(c,z_c)$ to Bob, where $c \in \{0,1\}$ is also a random bit.

How can I design a protocol, so that it will realize OT securely with access to R only once at the beginning of the protocol?

I am thinking that the protocol should be as following:

First, Alice inputs $(x_0,x_1)$, then she gets $(x_0 \oplus z_0,x_1 \oplus z_1)$ as output, thus learning nothing. Now Bob gets $(c,z_c)$, treat $c$ as his input $b$, then he can recover $x_c$ from $(x_0 \oplus z_0,x_1 \oplus z_1)$.

I don't know if it will work, or maybe I am working in the wrong direction?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
9
$\begingroup$

No, as written, your protocol doesn't work -- the problem is that Bob is supposed to be allowed to choose $b$, your protocol selects a random one for him.

However, it is close -- here is a modification that I believe does work:

First, suppose Alice has her values $(x_0, x_1)$, and Bob has his bit $b$.

They run their Random functionality R, and so Alice gets the values $(z_0, z_1)$, and Bob gets the values $(c, z_c)$.

Now, Bob sends the Alice the bit $e$ defined as $e = b \oplus c$; Alice sends back a pair of values $(y_0, y_1)$ defined as $(y_0, y_1) = (x_0 \oplus z_e, x_1 \oplus z_{1 \oplus e})$.

Bob then computes $z_c \oplus y_b = x_b$.

I claim that Alice gets no information about the value of $b$, and that Bob gets no information about the value of $(x_{1 \oplus b})$, and thus this is a valid Oblivious Transfer function.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks, phocho, so if I do the modification for random OT as following:Alice gets random bits $(S_A, P_A)$ and Bob gets random bits $(S_B, P_B)$ with one condition that is $S_A+S_B=P_A P_B$, how should the protocol be modified to realize OT? I think with that condition $(S_A,P_A)$ and $(S_B,P_B)$ can be mapped into $(z_0,z_1)$ and $(c,z_c)$ one by one, but I couldn't really write the mapping out explicitly. Do you have any idea about that? $\endgroup$
    – huyichen
    Commented Nov 2, 2011 at 22:03
  • 1
    $\begingroup$ Well, the obvious approach would be to notice that if Bob gets $P_B=0$, he knows the value $S_A$, and if Bob gets $P_B=1$, he knows the value $S_A+P_A$, and so you could attempt to run the above protocol with $z_0=S_A$ and $z_1=S_A+P_A$. It doesn't appear that the information that Alice gets about $S_B$ or $S_B+P_B$ allows her to deduce $b$. However, there is a subtle problem with that; the above protocol implicitly assumes that the values $z_0$, $z_1$ and $c$ are both uniformly and independently distributed. It's not clear that's true with this random generator. $\endgroup$
    – poncho
    Commented Nov 3, 2011 at 3:17

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.