Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I know of a solution. But this has a limitation that information is partially passed around and there needs some trust level. I'm wondering if any variant of public-private key (e.g. RSA) algorithm can solve this.

--Spoiler Alert: solution without RSA--

Salary of A:  x
Salary of B:  y
Salary of C:  z
Salary of D: u

A passes to B  (x + a) where a is a number that A knows
B takes this a passes to C (x + y + a + b)
C takes this and passes to D (x + y + z + a + b + c)
D takes this and passes to A (x  + y + z + u + a + b + c + d)

Now one after another they strip their constants. Ex: A now passes to B:  x + y + z + u + b + c + d (She has stripped of A) and B passes to C after stripping of her constant (b).

Thus Finally D gets x + y + z + u + d. She takes away her constant and now she has x + y + z + u.
So she can publish the average (x + y + z + u) /4.
share|improve this question
2  
your solution fails in some cases. Say x=y=z=0. Then D sees that x+y+z+u+d=u+d, and deduces x+y+z=0 hence (assuming salaries are positive) x=y=z=0. –  mt_ Aug 1 '11 at 19:23
1  
I've heard of this type of problem - it falls under the purview of secure multiparty computation. Sounds extremely interesting - another reason why I wish I knew more cryptography. –  anon Aug 1 '11 at 19:27
9  
@mt_ Good observation. The "naive" statement that the protocol does not leak or give away any information is incorrect, thanks to your counter-example. The right guarantee is slightly more technical: the "protocol" does not leak any more information than just the "answer" (i.e., the combined salary $x+y+z+u$) does. In other words, it is no fault of this protocol that $D$ can infer that her colleagues do not earn a penny; any protocol--in fact, even a hypothetical one where a trusted angel magically just announces the sum to the world--would allow her to. Hopefully it made sense. :-) –  Srivatsan Aug 1 '11 at 19:52
    
In this solution, the two employees before and after an employee E together have enough information to deduce E's salary, since from the differences between the values passed to and by E they can deduce the salary plus the constant from the first round and the constant from the second round. –  joriki Aug 23 '11 at 5:15
    
@anon you might be interested in checking out papers like this one pdf. –  user2468 Feb 22 '12 at 3:38
add comment

2 Answers 2

Look up homomorphic encryption on Wikipedia.

share|improve this answer
1  
It's not immediately clear to me how this can be used for secure computation. My first idea was that each employee specifies a public key and the salaries are encrypted with all public keys, added/multiplied as required by the homomorphism and then decrypted to find the sum. But that would allow for finding the salaries by encrypting all plausible numbers and comparing with the known results. How can this be prevented? I didn't find any concrete algorithms following some of the links given under secure multiparty computation. –  joriki Aug 24 '11 at 7:04
    
Cryptography is always defined with respect to some complexity assumptions, so you need to find a way to add more security. You can, for example, add some lower order digits (i.e. some random number of microdollars) to prevent enumeration of the kind you suggest. The amount of spurious information you add is the security parameter, the security of scheme is defined with respect to which. –  Yuval Filmus Aug 24 '11 at 19:11
add comment

Why not do it this way?

Get four randomly generated numbers, $m, n, l, k.$

Four persons' salaries are $a, b, c, d.$

Write the $4$ random numbers in four pieces of paper, put the paper into a jar. People draw the paper, substract her own salary with the random number, submit the answers. Then they together can add the answers together and add back $(m+n+l+k)$. This will give them the sum of their salaries and so the average.

Since the numbers are randomly distributed, no one would know exactly what numbers others get so they cannot recover from the substracted numbers to the original salaries of others.

share|improve this answer
2  
This does not truly leave everyone with minimal inference about others' salaries. All parties will know each of the three random numbers they did not draw and each of the three differences that they did not submit. This leaves them with a discrete set of possibilities for guessing the others' salaries. From any one person's perspective, there are only $9$ values that a coworker's salary could be. I think this is less than the ideal where all anyone could infer was the sum of the other three salaries. –  alex.jordan Feb 22 '12 at 3:23
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.