Take the 2-minute tour ×
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.

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

share|improve this question
1  
Looks like HW...how have you already tried to approach this problem? –  DrLecter Nov 20 '13 at 7:58
    
@DrLecter I have edited my question. –  freak_warrior Nov 20 '13 at 8:17
2  
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. –  figlesquidge Nov 20 '13 at 11:10
2  
@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. –  DrLecter Nov 20 '13 at 12:19
1  
Is $f(a,b,c)=a+b+c$ or $a\oplus b\oplus c$? –  mikeazo Nov 20 '13 at 12:58
show 2 more comments

1 Answer

up vote 2 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

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.