1
$\begingroup$

Consider 3 parties, Alice, Bob and Charlie. Suppose each party has a bit as input, i.e. Alice, Bob and Charlie hold $a, b, c \in \{0, 1\}$ respectively. Show how construct a scheme with which they can compute the function $f (a, b, c) = a \oplus b \oplus c$ such that the following are satisfied:

(1) All parties learn $f(a, b, c)$ at the end.

(2) No party can learn more about the other party's input than what they can infer from $f(a, b, c)$ and choosing their own input wisely.

My attempt: A chooses $r_1,r_2\in\{0,1\}$, B chooses $s_1,s_2,\in\{0,1\}$, and C chooses $t_1,t_2\in\{0,1\}$ randomly. Then dealer of respective secrets (bold) distribute 3 shares to each party in the following manner.

$A: \it{\bf{a\oplus r_1 \oplus r_2}}, s_1, t_1$

$B: r_1, \it{\bf{b\oplus s_1 \oplus s_2}}, t_2$

$C: r_2, s_2, \it{\bf{c\oplus t_1 \oplus t_2}}$.

To reconstruct the secret $a\oplus b\oplus c$, they can compute their sum of shares,

$A: (a\oplus r_1 \oplus r_2)\oplus s_1\oplus t_1$

$B: r_1\oplus( b\oplus s_1 \oplus s_2)\oplus t_2$

$C: r_2\oplus s_2\oplus( c\oplus t_1 \oplus t_2)$.

$\endgroup$
  • 1
    $\begingroup$ Looks like HW...how have you already tried to approach this problem? $\endgroup$ – DrLecter Nov 20 '13 at 7:58
  • $\begingroup$ @DrLecter I have edited my question. $\endgroup$ – freak_warrior Nov 20 '13 at 8:17
  • 2
    $\begingroup$ Your current method suggests to be you've slightly misunderstood the question. $a,b,c$ are created by A,B and C respectively. The protocol you describe requires them to be known in advance by some 4th party, which does not exist in the scenario given. $\endgroup$ – figlesquidge Nov 20 '13 at 11:10
  • 2
    $\begingroup$ @freak_warrior I guess in the last step you mean compute and publish their sum of shares. Yes, then it works and A B and C can compute $f(a\oplus b \oplus c)$ without learning the other's inputs. $\endgroup$ – DrLecter Nov 20 '13 at 12:19
  • 1
    $\begingroup$ Is $f(a,b,c)=a+b+c$ or $a\oplus b\oplus c$? $\endgroup$ – mikeazo Nov 20 '13 at 12:58
2
$\begingroup$

Your protocol is good (assuming an honest-but-curious adversary model). As DrLecter pointed out, each party will need to publish their sum of shares. To recover the answer, each party then simply xors all published values.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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