Say three old schoolmates meet after some time and they go out for a dinner. Naturally, their conversation goes over what they are doing and how much they are earning. They are just curious to know what the average earnings of three successful businessman is around, but they do not want to share with the others how much they earn because they will feel ashamed to know that they earn less than the others.

So, the problem is, how do they compute their average wages, without revealing to each other one's wage?

They could of course call the waiter and whisper to his ear their wages, and then the waiter would tell them what the average wage is. But then, they would have to kill the, oh poor, waiter... So, in order for the curiosity not to kill the waiter, another solution has to be found, especially if these businessmen have not physically met and they all live in different places, so the 'waiter' concept cannot easily be applied.

Indeed, there is one solution. Imagine the following very easy protocol:

• Businessman A, adds to his wage a secret random number R. He then encrypts the result with the public key of businessman B and sends him the result.
• B receives the message, decrypts it with his private key, and reads the result. He cannot determine what the wage of A is, because A had added to it a random number, unknown to B. Then B, adds to this result his wage and encrypts the latest result with the public key of C. He sends it to C.
• C likewise, decrypts the message with his own private key, and adds his wage to the result. He encrypts the result with A's public key and sends it to him.
• Lastly, A decrypts the message with his key, takes the result and subtracts the random number R that he had added at the beginning. So A is now presented with the sum of all three wages. He divides by three et voila, the average wage, without anybody knowing anybody's wage!
This kind of solution is called a secure multiparty computation.
Here is another approach to this very same problem. .

Bibliography

Applied Cryptography, Bruce Schneier