Three coworkers would like to know their average salary. How can they do it, without disclosing their own salaries?
The key is to scramble the sum with unknown/unshared data. The scramble must be reversible and when reversing it must not effect the sum.
Answer on the web:
So each person adds a random number(Rn) plus there salary(Sn) to the sum(Sum) and hands it to the next one. And then in the second round they each deduce there random number
(round 1) Sum0 = S1 + R1 Sum1 = S1 + S2 + R1 + R2 Sum2 = S1 + S2 + S3 + R1 + R2 + R3 (round 2) Sum3 = S1 + S2 + S3 + R2 + R3 Sum4 = S1 + S2 + S3 + R3 Sum5 = S1 + S2 + S3 And final they divide by the number of people Average(6) = (S1 + S2 + S3)/3
Here is the proof:
For person 1
Starts with: R1 S1 Sum0 = S1 + R1 Sum2 = S1 + S2 + S3 + R1 + R2 + R3 Sum3 = S1 + S2 + S3 + R2 + R3 Sum5 = S1 + S2 + S3 Can calc R2 + R3 = Sum3 - Sum5 So he finally knows R1 S1 R2 + R3 S2 + S3
For person 2
He starts with: R2 S2 Sum0 = S1 + R1 Sum1 = S1 + S2 + R1 + R2 Sum3 = S1 + S2 + S3 + R2 + R3 Sum4 = S1 + S2 + S3 + R3 Sum5 = S1 + S2 + S3 He can calc: R3 = Sum4 - Sum5 He finally knows knows R2 R3 S2 S1 + R1 S1 + S3
For person 3
He Starts with: R3 S3 Sum1 = S1 + S2 + R1 + R2 Sum2 = S1 + S2 + S3 + R1 + R2 + R3 Sum4 = S1 + S2 + S3 + R3 Sum5 = S1 + S2 + S3 He can calc: S1 + S2 = Sum5 - S2 R1 + R2 = Sum2 - S1 + S2 He finally knows: R3 S3 S1 + S2 R1 + R2
Here is a much stronger answer
It requires an 2 or more arbitrators in the system, At the end of each Sum stage the summer chooses a random arbitrator who then adds his own random value to the sum.
Once Sum5 stage is complete the arbitrators each in turn recieve the sum and deduct out the total of the random numbers they added in. As a result the computation becomes
(round 1) Sum0 = S1 + R1 + A0 Sum1 = S1 + S2 + R1 + R2 + A0 + A1 Sum2 = S1 + S2 + S3 + R1 + R2 + R3 + A0 + A1 + A2 (round 2) Sum3 = S1 + S2 + S3 + R2 + R3 + A0 + A1 + A2 + A3 Sum4 = S1 + S2 + S3 + R3 + A0 + A1 + A2 + A3 + A4 Sum5 = S1 + S2 + S3 + A0 + A1 + A2 + A3 + A4 + A5 Sum6 = S1 + S2 + S3 + A0 + A2 + A4 Sum7 = S1 + S2 + S3
Hence its much more harder to break
Hi I did not understand how the second person knows Sum(2)? Because the idea should be that Person 1 gives his sum to Person 2 and then he gives the collective sum to Person 3. This total sum with the rand values is Sum(2). Sum(2) is passed to Person 1. Person 2 does not see that. When it comes to him Sum(3) already.
ReplyDeleteAm I missing something?
Hi Irem, you are correct I messed up the original check and gave Person2 knowledge of Sum2 wwhich was a mistake. Ill rewrite the original post with the corrected proofs.
ReplyDelete