I am trying find a transfer method for this problem. Suppose Alice and Bob both has access to a function $\text{F}$ with two parameters. $\text{F}(x,y)$ randomly returns $p$ to alice and $q$ to Bob such that $x\times y=p \oplus q$. Now as per rules of Oblivious Transfer, Alice has $s_0$ and $s_1$ and Bob has $c$. Bob wants to learn $Sc$. The catch is alice can transfer at most one bit in total to bob, that means they can communicate just once. How can Bob learn $Sc$ using this function?

  • $\begingroup$ possible duplicate of Protocol for Randomized Oblivious Transfer? $\endgroup$
    – poncho
    Commented Jan 25, 2014 at 19:34
  • 1
    $\begingroup$ Nope; the solution listed as a duplicate doesn't meet the criteria; Alice sends back two bits, not just one... $\endgroup$
    – poncho
    Commented Jan 25, 2014 at 20:12
  • $\begingroup$ @poncho If the solution listed as a duplicate doesn't meet the criteria, why leave the close vote? Is it a duplicate nevertheless? Maybe I'm confused because it's late (2AM) and I could imagine there's an obvious reason, but somehow I'm not getting it... probably due to the "Nope" which contradicts the "dupe" vote. $\endgroup$
    – e-sushi
    Commented Jan 26, 2014 at 1:01
  • $\begingroup$ I am finding this question hard to follow. What do you mean by a "transfer method"? What is $Sc$? Do you mean $s_c$? What counts as bits transferred to Bob? Can they invoke $F$ as many times as they want? Who provides the inputs to $F$ (does $x$ come from Alice and $y$ from Bob)? Are we guaranteed that $p,q$ are chosen randomly subject to the condition that $p \oplus q = x \times y$? Please edit the question to make the problem statement clearer. $\endgroup$
    – D.W.
    Commented Jun 23, 2014 at 1:37

1 Answer 1


The obvious approach is to help Bob learn $s_0 \oplus (s_0 \oplus s_1) \times c$, presumably using $F$ to help him learn this information. So, here is the natural protocol:

  • Alice and Bob invoke $F$. Alice provides the input $s_0 \oplus s_1$, Bob provides the input $c$. Alice learns $p$ and Bob learns $q$, where we are guaranteed that $p \oplus q = (s_0 \oplus s_1) \times c$.

  • Alice sends $p \oplus s_0$ to Bob.

Notice that, with this information Bob can compute $s_c$. I leave it as an exercise to you how to do that.

Also, notice that Bob learns only one of $s_0,s_1$. I leave it to you as an exercise to prove that.

Finally, notice that if $F$ does not disclose anything about its inputs to either part, then Alice does not learn anything about Bob's bit $c$.


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.