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.
  • 3
    $\begingroup$ 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. $\endgroup$ Aug 1 '11 at 19:23
  • 1
    $\begingroup$ 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. $\endgroup$
    – anon
    Aug 1 '11 at 19:27
  • 11
    $\begingroup$ @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. :-) $\endgroup$
    – Srivatsan
    Aug 1 '11 at 19:52
  • $\begingroup$ 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. $\endgroup$
    – joriki
    Aug 23 '11 at 5:15
  • $\begingroup$ @anon you might be interested in checking out papers like this one pdf. $\endgroup$
    – user2468
    Feb 22 '12 at 3:38

Look up homomorphic encryption on Wikipedia.

  • 1
    $\begingroup$ 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. $\endgroup$
    – joriki
    Aug 24 '11 at 7:04
  • $\begingroup$ 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. $\endgroup$ Aug 24 '11 at 19:11

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.

  • 3
    $\begingroup$ 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. $\endgroup$ Feb 22 '12 at 3:23
  • $\begingroup$ We could reduce the leaked information as close as we want to zero by having each participant submit a sufficiently large set of random numbers instead of only one. Narrowing down the number of possibilities to $3000\choose1000$ is not that helpful. $\endgroup$
    – MJD
    Jul 27 '18 at 12:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.