0

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

l4m2
  • 211
  • 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? – Adayah Jul 27 '18 at 11:22
  • @Adayah right, an error should be generated and not known by someone – l4m2 Jul 27 '18 at 11:42

1 Answers1

2

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.

David G. Stork
  • 29,774
  • 1
    No. Person 1 and 3 can get 2's score – l4m2 Jul 27 '18 at 11:18
  • That is when Person 1 and person 2 are dishonest... colluding to get another's score. "Honest" means being truthful and not cheating the system. – David G. Stork Jul 27 '18 at 11:19
  • See https://math.stackexchange.com/questions/55014/how-can-four-employees-calculate-the-average-of-their-salaries-without-knowing-o or https://math.stackexchange.com/questions/921099/why-does-this-method-for-the-average-salary-problem-fail? or https://math.stackexchange.com/questions/2156708/how-to-find-out-the-average-salary – Gerry Myerson Jul 27 '18 at 11:28
  • Person 2 is honest, but 1 and 3 aren't – l4m2 Jul 27 '18 at 11:39
  • Of course. That's why my answer is correct for the condition I explicitly listed: "If all are honest..." All. – David G. Stork Jul 27 '18 at 12:50