Dining cryptographers

This problem was first proposed by David Chaum in 1988 to illustrate an anonymous communication protocol. In the original problem, three cryptographers are having a dinner at a restaurant. At the end the waiter informs them that the dinner has already been paid, either by one of them, or by their employer the National Security Agency (NSA). The cryptographers want to know whether the NSA paid for the dinner, without divulging the identity of their colleague if it’s not the case.

Therefore they set up a two stages protocol. In the first stage, each pair of cryptographers determine a random one-bit shared secret. In the second stage, each cryptographer publicly announce a bit, which is the result of the exclusive-or (XOR) between the shared bits he knows if he didn’t pay for the meal, or the contrary if he is the one who paid. Finally, by taking the XOR between all the announced bits the cryptographers are able to determine that the NSA paid if the result is 0 or  that one of them paid if the result is 1.

In QUAIL we implement this protocol for a number N of cryptographers arrange in a ring. Each cryptographer share two bits with his two neighbours. The attacker can be one of the cryptographer if we allow him to observe 2 of the coins tossing, or an external attacker if only the public declaration of each cryptographer and the final output are observable.

We analyse the protocol when the attacker is one of the cryptographer. The table below shows the leakage for different number N of cryptographers and different probability of coin. The results show that the more the coin is deterministic (with a probability close to 0 or 1), the greater the leakage. When the probability is 0 or 1 the leakage is equivalent to the bit size of the secret, i.e. the logarithm in base 2 of N+1, proving that the whole secret gets leaked, and thus the attacker learns the identity of the payer, whoever he is.