Computing an Average Salary Without Revealing Anyone's Salary
Eight quants on a desk are curious about the average salary of the group, but none of them is willing to disclose his or her own salary to anyone else. They have no trusted third party and no computer they all trust; all they can do is talk to each other and pass slips of paper.
Design a procedure that lets the eight quants compute the exact average salary of the group while guaranteeing that no quant learns any other individual's salary (assuming no two quants collude).
Hints
- Any protocol where a running total is passed around leaks the first person's salary to the second person. Find a way to hide the starting point.
- The first quant can add a secret random number to his salary before passing the total on. Now the second quant sees a number that tells him nothing.
- After all eight have added their salaries, the sum comes back to the first quant, who subtracts the secret random number and divides by 8. Every intermediate total is masked by the secret offset.
Worked Solution
How to Think About It: The obstacle is not the arithmetic but the information flow. Whoever receives a number must not be able to reconstruct anyone's salary from it. Masking the very first contribution with a secret random offset makes every intermediate value uninformative, while the offset is trivially removed at the end.
Approach: Additive masking around a ring.
Formal Solution:
*Step 1 -- Setup.* Label the quants $1, 2, \ldots, 8$ with salaries $s_1, \ldots, s_8$. Arrange them in a ring: quant $i$ passes to quant $i+1$, and quant $8$ passes back to quant $1$.
*Step 2 -- Masking.* Quant $1$ privately picks a random number $R$ (large enough that $s_1 + R$ looks like noise, and known only to quant $1$). He writes $T_1 = s_1 + R$ on a slip and passes it to quant $2$.
*Step 3 -- Accumulation.* Each subsequent quant $i$ receives $T_{i-1}$, adds his own salary, and passes $T_i = T_{i-1} + s_i$ to the next quant. After quant $8$, the slip returns to quant $1$ carrying $$T_8 = R + s_1 + s_2 + \cdots + s_8 .$$
*Step 4 -- Unmasking.* Quant $1$ subtracts $R$ to get $S = \sum_{i=1}^8 s_i$ and announces the average $S / 8$.
*Step 5 -- Why nothing leaks.* Quant $2$ sees only $s_1 + R$, which is uninformative because $R$ is unknown to him. Quant $i \ge 3$ sees $R + s_1 + \cdots + s_{i-1}$, a sum masked by $R$ and containing several salaries, so no individual value can be extracted. Quant $1$ sees $R + S$ and learns only $S$, which everyone learns anyway from the announced average. The published average itself reveals only the total. (If quants $i-1$ and $i+1$ collude they can recover $s_i$ by differencing, which is why the guarantee assumes no collusion; a stronger version has each quant split his salary into random shares handed to different people.)
Answer: Pass a slip around the ring: quant 1 starts with (salary + secret random number $R$), each of the other seven adds his salary, and quant 1 finally subtracts $R$ and divides the total by 8 to announce the average. Every intermediate total is masked by $R$, so no individual salary is revealed.
Intuition
A running sum leaks whatever the previous person added, unless the sum itself is unreadable. Adding a secret offset chosen by the first person makes every partial total look like a random number, so each quant learns nothing from what they receive, and the offset is removed at the end by the only person who knows it. This is the simplest instance of secure multi-party computation via additive masking, the same idea behind secret sharing and privacy-preserving aggregation of trading positions or model gradients across parties that do not trust each other.