A simple zero knowledge protocol. n professors of theoretical computer science gather in a room. They want to compute their average salary, but each is ashamed of how little money she or he earns. Use of a zero knowledge protocol is ideal here.
Note that if n=2, then there's not much point to the protocol. By learning the average salary of Alice and Bob, Alice can immediately determine Bob's salary: twice the average, minus her own salary. Even in this case, the zero knowledge guarantee is preserved -- it just doesn't give anything.
First, our professors agree on a big upper bound: no professor makes anything close to N=$1000000, especially not a TCS type. All computations will take place modulo n*N. If we know the sum of the salaries modulo n*N, then we know the sum -- it's just that number, as each professor earns between $0 and N. Our protocol will compute this number. By dividing by n, we determine the average salary.
Seat the professors in a circle. Professor #i's salary will be $Xi. Professor #1 cannot tell professor #2 her salary, or she breaks the zero knowledge guarantee. Instead, she picks a random number R1 from a uniform distribution on [0,N), writes down R+X1 (mod n*N) on a piece of paper, and passes it to professor #2. Professor #2 picks a random number R2, adds R2+X2 (mod n*N) to the sum she got, writes that down on a new piece of paper, and passes that to professor #3. Continue all the way around the circle, until the piece of paper returns to professor #1.
Professor #1 now has a piece of paper with the number R1+R2+...+Rn+X1+X2+...+Xn (mod n*N) written down on it. She subtracts R1 (not forgetting to give the result modulo n*N), which she knows, from it, writes it down, and passes it to professor #2. Each professor continues to subtract his or her Ri from the number, until again it reaches professor #1. Professor #1 announces the sum of the numbers, and all know their average salary.
It can be shown that this protocol gives zero information. For instance, in the first round professor #2 gets the number R1+X1, which can be shown to give no further information about X1. In the second round, he gets the sum of all Xi's, plus some random numbers. But he's anyway going to end up with the sum of all Xi's, unobfuscated by any random numbers, so this too gives no additional information.
Apart from the information known initially to each professor (information about Prof. Alice Bobinskov's salary may have been revealed in the paper -- Uni Awards Scandalous $20000 Raise to Prof Who Proves P = NP gives the information that she earns at least $20000...) and the information gleaned from knowing the sum, this protocol gives zero additional knowledge. All this if we assume nobody cheats.
| 
