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

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ Looks like HW...how have you already tried to approach this problem? $\endgroup$
    – DrLecter
    Commented Nov 20, 2013 at 7:58
  • $\begingroup$ @DrLecter I have edited my question. $\endgroup$
    – meta_warrior
    Commented Nov 20, 2013 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$
    – Cryptographeur
    Commented Nov 20, 2013 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
    Commented Nov 20, 2013 at 12:19
  • 1
    $\begingroup$ Is $f(a,b,c)=a+b+c$ or $a\oplus b\oplus c$? $\endgroup$
    – mikeazo
    Commented Nov 20, 2013 at 12:58

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

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.