7
$\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. 
  • 3
    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.2011-08-01
  • 1
    I've heard of this type of problem - it falls under the purview of [secure multiparty computation](http://en.wikipedia.org/wiki/Secure_multi-party_computation). Sounds extremely interesting - another reason why I wish I knew more cryptography.2011-08-01
  • 11
    @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. :-)2011-08-01
  • 0
    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.2011-08-23
  • 0
    @anon you might be 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