2

In my Computer Science class, we were introduced to the Average Salary problem, where a group of people want to determine their average salary, but they don't want anyone to be able to determine the salary of anyone else.

I proposed a solution which I later looked up and found to be a fairly common one, wherein everyone writes down several numbers on separate pieces of paper that add up to their salary. The papers are then collected in a hat, totaled, and divided by the number of people.

My professor said that he was looking for a solution that only involved direct communication as to avoid the use of "trusted hardware". However, he also told me that my solution was flawed because some information is unnecessarily revealed, and, I must assume for the sole purpose of tormenting me, he said we would go over it later when he revealed the solution to the rest of the class.

He also told me my solution was still inadequate when I said that the numbers could be both positive and negative, and everyone was to submit an arbitrary amount of numbers.

My question is not what is the ultimate solution to this problem, but rather, what is wrong with mine? What information could be revealed from arbitrary numbers that when added up equal the total salary?

HashFail
  • 185
  • Information is revealed to whoever adds up the numbers on the papers. More precisely, the person doing the adding up now knows a finite number of possibilities for everyone's salaries, the possibilities being given by considering all possible ways of splitting up the papers into $n$ disjoint subsets ($n$ the number of people). – Qiaochu Yuan Sep 06 '14 at 04:50
  • (If it's not a person doing the adding but, say, a computer, then you could've just fed the salaries to the computer in the first place.) – Qiaochu Yuan Sep 06 '14 at 04:52
  • @Jake C: I rather like your idea. If you don't mind a lot of slips of paper, you could have everyone write $1 on as many slips as their salary, and throw all those into the hat, and continue with your method. I don't think that would give away any individual information. (Or if that's too many slips, you could go by $100s or $1000s, possibly with one odd slip to make the amount exact.) – paw88789 Sep 06 '14 at 05:24
  • @paw88789: I think the problem is that you have to assume that nobody peeks into the hat too soon (or looks at exactly how big everyone's stack of slips is), which seems to tie into the prof's comment about trusted hardware. It'd probably work pretty well in practice, though... – Micah Sep 06 '14 at 05:30
  • @Micah I think you're right about the peeking. That my have been what my prof was getting at before we ran out of time and I had to run to a different class. Thanks for the input everyone. – HashFail Sep 06 '14 at 14:27
  • @QiaochuYuan Your answer makes sense, and I'm pretty sure this is along the lines of what my prof meant, thanks. – HashFail Sep 06 '14 at 14:29
  • @paw88789: You also have to assume that nobody is looking at how many slips of paper everybody else is stuffing into the hat. – Qiaochu Yuan Sep 06 '14 at 18:38
  • @Qiochu Yuan and all: How's this: Everyone gets 30 slips (could be more, but 30 slips will accommodate salaries up to about a billion dollars). Each person's set of slips has a slip numbered $1$, one numbered $2$, one numbered $4$, ..., one numbered $2^{29}$. Pick the slips that add up to your salary and circle the numbers on those slips, leaving the other slips uncircled. Then everyone throws their 30 slips into the hat. However, it seems like we may be headed to needing some sort of encryption scheme with all the info that seems to be collectible in the various scenarios. – paw88789 Sep 06 '14 at 19:28

2 Answers2

1

Assembled from comments:

There are (at least) two problems. First, information is revealed to whoever adds up the numbers on the papers. More precisely, the person doing the adding up now knows a finite number of possibilities for everyone's salaries, the possibilities being given by considering all possible ways of splitting up the papers into n disjoint subsets (n the number of people).

If you don't mind a lot of slips of paper, you could circumvent this by having everyone write \$1 on as many slips as their salary, and throw all those into the hat, and continue with your method. I don't think that would give away any individual information. (Or if that's too many slips, you could go by \$100s or \$1000s, possibly with one odd slip to make the amount exact.)

However, you then still run into the second problem: you have to assume that nobody peeks into the hat too soon (or looks at exactly how big everyone's stack of slips is). That is, everyone has to trust that the "hardware" the solution is running on behaves the way it should.

Micah
  • 38,108
  • 15
  • 85
  • 133
1

For those still wondering, my professor's main gripe with my solution was the use of pen and paper, since the answer he was looking for required only direct communication. He told me that the solution doesn't really reveal any useful information that he could think of, but he wanted to keep any potentially usable information from being revealed (the key being that only truly random numbers should be communicated). He did, however, agree with Qiaochu Yuan's suggestion about there being a finite number of possible combinations of the papers.

His solution was to have everyone tell everyone else a number. If there were N people, the first N-2 numbers would be selected at random between 0 and P, an arbitrarily number larger than the sum of the salaries (his suggestion was 10 times the GNP of the world). The last number would be the person's salary minus the sum of all the numbers, all operations being modular about P. Each person would then total all the numbers they received and announce the total. Finally all the numbers would be added together for the sum of all salaries. Again, all operations are modular.

This way, no group of people smaller than N-1 could come up with any useful information.

HashFail
  • 185