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