To motivate my question, I will describe a related problem and then give a solution to it. My question will then be a variant of this problem.

N individuals sit around a table and want to compute the average of their salaries. They wish to do this in a manner such that no private information is leaked. This is to say no one obtains any information (regarding the other's salaries) that he couldn't deduce from the public information.

More formally we assume: (1) all of the salaries are non-negative integers bounded by B (2) everyone behaves honestly and doesn't attempt to halt the process (3) no subset of individuals will collude (4) there are secure private lines of communications between all participants (5) all of this information is well known (6) there is no outside trusted party.

Question 1: Is it possible for the N individuals to collectively compute the average without leaking any information? We say information is leaked if any individual has any information at the end of the process regarding anyone else's salary that he couldn't have deduced from knowing his own salary and the average.

The answer is Yes. It suffices to compute the sum of the salaries. Set S = 10*N*B. Now the first individual (Alice) chooses a uniformly random number between 0 and S-1 and adds this to her salary mod S. She then passes the sum to her neighbor, Bob, who adds his salary. This continues around the table until Zoey (the last participant) passes the number back at Alice. Alice subtracts off the random number and announces the sum to the group.

Here are two related questions:

Question 2: Is it possible for the group to compute the maximum salary (subject to the constraints above) without leaking any information?

Question 3: Can we remove the assumption that a bound on the size of the salaries are known in advance from the algorithm given above.

Additional Note: In Question 2 we want to compute only the maximum without providing any other information. One can note that, say, the entire distribution of salaries could be computed and communicated to the group by computing moments of the sequence via the method above. This would give the maximum (however a lot of other information as well).

4more comments