Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|improve this question
up vote 6 down vote accepted

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.

share|improve this answer
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? – huyichen Nov 2 '11 at 22:03
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. – poncho Nov 3 '11 at 3:17

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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