$n$ guys each have a score in $[0,100]$, and they want to know their average. However they don't want their score to be known by others, even if the other $(n-1)$ ones are all dishonest. They can accept a not-that-accurate result for safety.
- If everyone is honest, they can get their average score approximately
- If someone is honest, no matter how others do, they can't get his score that near.
A physical solution is:
- Place $k$ white balls and $k$ black balls in a box
- Let everyone who get score $a$ put $a$ white balls and $(100-a)$ black balls into the box
- Randomly pick $m$ balls from the box, assuming there are $w$ white balls
- The average score is $\frac1n[\frac wm(2k+100n)-k]$
Is it possible on a net environment(any thing belong to someone, no trusted third-party)?
If all are honest, this is a classic problem in security and cryptography.
Person 1 generates a random number $r$ known only to her, then adds her score to it, to get $x_1 + r$, and passes it to person 2. Person 2 does not know person 1's score because she doesn't know the random number $r$. Then person 2 adds her score to get $x_1 + x_2 + r$ and passes it to person 3. Person 3 knows neither person 1's nor person 2's score because person 3 does not know $r$. And so on through the entire set of people.
Then the total is returned to person 1, who subtracts the secret $r$ and divides by the number of people.
Done.