Why does this method for the average salary problem fail?

Question

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?

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

Answer 2

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.