The Dining Cryptographers Problem (1988) [pdf](dl.dropboxusercontent.com) |
The Dining Cryptographers Problem (1988) [pdf](dl.dropboxusercontent.com) |
To simplify, let's say heads is 1 and tails is 0. Then the scheme can be defined using XOR. r1 represents the value of the coin Alice and Bob can see, r2 represents the value of the coin Alice and Charles can see, and r3 represents the value of the coin Bob and Charles can see.
Let x be whether Alice paid, y1 whether Bob paid, and y2 whether Charles paid.
Let * denote XOR. Alice computes v1 = r1 * x * r2, Bob computes v2 = r1 * y1 * r3, and Charles computes v3 = r2 * y2 * r3. They all then compute v1 * v2 * v3 which is equal to x * y1 * y2. Since they each know one variable, (e.g. x for Alice), they can compute y1 * y2. Since they assume only one person paid, if y1 * y2 = 1, Alice knows either Bob or Charles paid.
The scheme is insecure if Alice wants to go against the protocol and tell Bob and Charles a different v1 (v1_1 for Bob and v1_2 for Charles), and Bob and Charles will announce the result.
Lets say Alice works for the NSA, and already knows that x = 0 (she didn't pay), and y1 * y2 = 0 (her employer didn't pay), but she wants to find out if y1 = 1 or y2 = 1.
She tells Bob v1_1 = r1 * 0 * r2. She tells Charles v1_2 = r1 * 1 * r2. Bob computes and announces v1_1 * v2 * v3 * y1 = r1 * 0 * r2 * r1 * y1 * r3 * r2 * y2 * r3 * y1 = y2. Charles computes and announces v1_2 * v2 * v3 * y2 = 1 * y1 = y3.
Another fundamental problem with DC networks is that a single malicious participant can completely disrupt communication, and the inherent anonymity of the protocol means detecting malicious actors is very difficult. Chaum introduces the idea of "trap rounds" that can be used to slowly exclude bad actors, but in actual use, trap rounds are rather inelegant and impractical.
Herbivore http://www.cs.cornell.edu/people/egs/papers/herbivore-tr.pdf is an implementation of DC networks that circumvents some of these problems by sorting participants into randomized groups of ~k participants, where k is a network-wide anonymity set constant. It avoids collusion by disallowing participants to choose which k-sized bucket they end up in, and limits Sybil attacks by requiring proof-of-work to join the network.
If the participants don't share or talk about the outcome at all, this particular attack is avoided, so it is a side channel and not a direct failure of the protocol itself.