Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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

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?

share|improve this question
possible duplicate of Protocol for Randomized Oblivious Transfer? – poncho Jan 25 '14 at 19:34
Nope; the solution listed as a duplicate doesn't meet the criteria; Alice sends back two bits, not just one... – poncho Jan 25 '14 at 20:12
@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. – e-sushi Jan 26 '14 at 1:01
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. – D.W. Jun 23 '14 at 1:37

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

share|improve this answer

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.