2
$\begingroup$

Here is a problem from section 2.3 (Thinking Out of the Box) section of the popular book by Xinfeg Zhou titled 'Quant salary':

Quant Salary

Eight quants from different banks are getting together for drinks. They are all interested in knowing the average salary of the group. Nevertheless, being cautious and humble individuals, everyone prefers not to disclose his or her salary to the group. Can you come up with a strategy for the quants to calculate the average salary without knowing other people's salaries?

The book provides the following solution:

Solution: This is a light-hearted problem with more than one answer. One approach is for the first quant to choose a random number, add it to his/her salary and give it to the second quant. The second quant will add his/her own salary to the result and give it to the third quant; and so on; the eighth quant will add his/her own salary to the result and give it back to the first quant. Then the first quant will deduct the 'random' number from the total and divide the 'real' total by 8 to yield the average salary.

The author mentions that there are alternative solutions to this problem. What are some alternative approaches?

Further Thoughts

The problem of secure multiparty communication is one of the interesting problems in the field of cryptography and security. While my knowledge of the same is limited, I wonder if there has been some work done on the design of an algorithm which can perform computation on an encrypted version of its inputs and decrypting the outputs can reveal the result of the computation without revealing any information about the inputs. That is, can we design an algorithm to which every quant can submit an encrypted version of their salaries, get the output and infer the average salary from the output either by decrypting it with a key known to any number of the quants or otherwise, which would allow them to infer the average salary without revealing any information about the individual salaries?

$\endgroup$
1

1 Answer 1

0
$\begingroup$
  1. (Optional) A base b other than 10 is chosen.
  2. Each participant writes the least significant digit/bit/unit of their salary in base b on a scrap of paper and puts it in a hat. These are scrambled and revealed. The sum is calculated by all participants. The carry digits/bits/units are put aside for subsequent rounds.
  3. Step 2 is repeated for the next-least significant digit/bit/unit, including the appropriate carry digit/bit/unit. The carry digits/bits/units will eventually be the sole contributors to the sum as each participant submits leading zeroes.
  4. When no carry digits remain (within reason, if everyone submits zero in the first round it is obvious that more rounds need to be played) then the sum may be divided by the total number of participants.

Limitations:

  1. if one participant's salary is an order of magnitude larger, this will be revealed (though not the participant's identity) even if the average would have appeared plausibly greater than each other participant's salary.

  2. it depends on a mechanism for obscurity (shuffling, hidden values in a hat) that cannot be replicated over a digital network without a trusted third party being involved.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.