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$
$\endgroup$
4
-
$\begingroup$ possible duplicate of Protocol for Randomized Oblivious Transfer? $\endgroup$– ponchoCommented 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$– ponchoCommented 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-sushiCommented 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
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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$.
