First thing on the menu: the Dining Cryptographers
Prepare to be served an extremely delicious cryptographic concept which illustrates an example of secure multi-party computation and anonymity.
Dining Cryptographers (DC)
The classical DC example includes three cryptographers who are enjoying a meal at a fancy restaurant. Their task is to find out whether one of them paid the bill or a third party, the NSA, paid it for them. The trick is that this information has to be revealed anonymously, without revealing the identity of the exact cryptographer who paid the bill.
Let me introduce you to our dining cryptographers: Alice, Bob and Carol.
Imagine a circular table with the cryptographers sitting around it (romantic candle not included). Each pair of cryptographers privately tosses a coin behind the menu, resulting in either 0 or 1.
For example, Carol and Bob toss a coin between them and store their value. Then, Carol and Alice toss their coin and store their value. Finally, Alice and Bob toss their coin and store their value.
After that, Carol compares the outcome from her coin flip with Alice to the coin flip with her and Bob.
This can be achieved by using the XOR function for Carol and Alice’s coin flip value vs Carol and Bob’s coin flip value. Each cryptographer then stores the XOR’d value for themselves. Now comes the smart anonymity feature of this entire scenario: if one of the cryptographers wants to signal that they paid the bill without revealing their identity, they XOR 1 to the value computed before (the XOR of coin flip outcomes). The result of who paid the bill is thus obstructed within all of these calculations.
Note: make sure to carefully examine the above picture and understand the functions of XOR operation as you will need this knowledge for our future posts and for general understanding of many crypto concepts.
We then have to XOR all of these values together in order to answer the question of who paid the bill. If the final answer is 0 then it was the NSA (or one of the cryptographers is not telling the truth) and if the answer is 1 then one of them anonymously admitted to paying the bill.
Answer = 0 i.e. all values cancel out → Thank you, NSA, for your generosity.
Answer = 1 i.e. one of the values was flipped → One of the cryptographers had to dip into the savings and pay the bill. (Note: NSA should probably review their employee benefits policy.)
DC has a number of limitations so please dine responsibly at your own risk. Some of the risks include collision and disruption.
At their next dinner meet-up, the cryptographers decide to optimise the DC solution and make it into a more practical anonymous system, that is also able to prevent denial of service and corrupted inputs. One fruitful example of their dinner discussion is the DC-nets.
Our Tartu adventures continue with a discovery of extravagant library menu at the UT Library building (spinach mash and aesthetic plates included) and dorm recipe experimentation (creamy baked apples & cinnamon oatmeal to start off the day).
Bon appetit!
