8
$\begingroup$

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. 
  • 0
    @$a$non you might $b$e interested in checking out papers like this one [pdf](http://www.iacr.org/cryptodb/archive/2001/CRYPTO/21390119.pdf).2012-02-22

2 Answers 2

2

Look up homomorphic encryption on Wikipedia.

  • 0
    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.2011-08-24
1

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.

  • 0
    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.2018-07-27