$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.

  1. If everyone is honest, they can get their average score approximately
  2. If someone is honest, no matter how others do, they can't get his score that near.

A physical solution is:

  1. Place $k$ white balls and $k$ black balls in a box
  2. Let everyone who get score $a$ put $a$ white balls and $(100-a)$ black balls into the box
  3. Randomly pick $m$ balls from the box, assuming there are $w$ white balls
  4. 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)?

others guessing someone's score by claiming their score be 0, where $n=1000, k=1000, m=25000, hisscore=50$

  • $\begingroup$ Do I understand correctly that all $n-1$ bad guys can claim their score is $0$ (even if it's not), so any good implementation of $\mathrm{average}$ must introduce enough of an error to make $n * \mathrm{average}( x, 0, 0, \ldots, 0 )$ sufficiently far from $x$ ? Otherwise, what does it mean that the bad guys can be dishonest? $\endgroup$
    – Adayah
    Jul 27 '18 at 11:22
  • $\begingroup$ @Adayah right, an error should be generated and not known by someone $\endgroup$
    – l4m2
    Jul 27 '18 at 11:42

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.



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.