## Wednesday, June 23, 2010

### Three coworkers sharing average salaries

Question:
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

#### 2 comments:

1. 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.

Am I missing something?

2. 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.