http://gurmeet.net/puzzles/

I rather liked this one: ("Perplexing Polynomials")

"Alice is allowed to choose an arbitrary polynomial p(x) of any degree with nonnegative integer coefficients. Bob can infer the coefficients of p(x) by only two evaluations as follows. He chooses a real number a and Alice communicates p(a) to him. He then chooses a real number b and Alice communicates p(b) to him."

Also: ("Average Salary")

"Four honest and hard-working computer engineers are sipping coffee at Starbucks. They wish to compute their average salary. However, nobody is willing to reveal an iota of information about his/her own salary to anybody else. How do they do it?"

I feel like the condition "nobody is willing to reveal an iota of information about their own salary to anybody else" isn't

*exactly*satisfied by the given solution. Or at least not as much as you'd like it to.

Call the four programmers Alice, Bob, Carol, and Dave. Alice chooses a random number rA uniformly between 0 and K-1 where K is assumed to be way bigger than any plausible sum of their 4 salaries. Alice says rA + sA to Bob, where sA is Alice's salary, and addition is assumed to be mod K. Bob says rA + sA + sB to Carol, Carol says rA + sA + sB + sC to Dave, Dave says rA + sA + sB + sC + sD to Alice, and Alice subtracts (mod K) rA to get the desired sum. The distribution of each message to every participant is uniformly random over [0,K-1], as desired, but there exist two sets of two participants who can collude to find the salary of the remaining two: together, Alice and Carol can compute (rA + sA + sB) - (rA + sA) = sB or (rA + sA + sB + sC + sD) - (rA + sA + sB + sC) = sD. Similarly, Bob and Dave can together compute (rA + sA) - (rA + sA + sB + sC + sD) + (sA + sB + sC + sD) = sA and (rA + sA + sB + sC) - (rA + sA + sB) = sC.

So you'd like to be necessary that

*all*the other participants in the protocol to find a given person's salary. (Certainly it is

*sufficent*if all other parties collude: the global sum is known, and they can just sum up all their salaries and subtract them from the global sum to find the non-colluder's) I think (but I'm not totally sure) the following protocol works for 4 people:

(Write rXYZ... to mean rX + rY + rZ + ... and sXYZ... to mean sX + sY + sZ + ....)

Alice generates rA, says rA + sA to Bob

Bob generates rB, says rAB + sAB to Carol

Carol generates rC, says rABC + sABC to Dave

Dave generates rD, says rABCD + sABCD to Alice

Alice subtracts rA in order to say rBCD + sABCD to Carol

Carol subtracts rC in order to say rBD + sABCD to Bob

Bob subtracts rB in order to say rD + sABCD to Dave

Dave subtracts rD in order to say sABCD to everyone.

The idea is that there's two rounds, and the ordering of the second round (ACBD) is sufficiently different from the first round (ABCD) that for any two participants that "surround" a third during the first round (in the sense that Alice and Carol together see the information going in and out of Bob, and so can deduce exactly how he's altering the randomized sum) are adjacent during the second round of the protocol, and vice-versa.

I went through and tediously checked all six pairs of participants and I think I convinced myself through sketchy linear-algebra reasoning that they can't find the specific salary of either of the remaining two participants, but I might have screwed up.

I wonder if there's a generalization to more people...

---

Ah, here's a generalization that works, but is more expensive than I expected. It uses Θ(n

^{2}) point-to-point messages and Θ(n) broadcast messages and requires Θ(n

^{2}) random numbers to be generated. In particular, for 4 participants, the below protocol requires 12 point-to-point messages, and 4 broadcast messages, and 8 random numbers, whereas the above requires only 7 point-to-point, 1 broadcast, and 4 random numbers.

Let there be n participants. Every participant x (whose salary is sx) generates n-2 random numbers r1, ... r(n-2), and sends n-1 messages, one to each participant y1, ... y(n-1) ≠ x. x sends r1 to y1, r2 to y2, ... r(n-2) to y(n-2), and (sx - (r1 + r2 + ... r(n-1))) to y(n-1). Each participant computes the sum of all the messages they receive during this first round, and broadcasts it. The sum of the messages each participant receives during the second round (which are all broadcast, so all participants receive the same set) is the desired sum of salaries.