Lets say that Alice, Bob and Charles play this game.
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.
Because Alice already knows the NSA didn't pay, the game effectively reduces to a two-participant model. Obviously, playing this game with only one other participant would provide no anonymity at all. n-1 colluders can deanonymize any DC network with group size n.
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.
I don't think your attack violates the security model of this protocol. One of the proofs in the paper is that if you have a network of good and bad nodes the bad nodes can use tricks like you posted to discover whether a good or bad node sent the message. I think that's all they can discover: did an attacker send this or not? But then again they already knew that, didn't they? So I think your attack is only interesting for 3 nodes.
[+] [-] A1kmm|11 years ago|reply
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.
[+] [-] samizdatum|11 years ago|reply
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.
[+] [-] SpikeGronim|11 years ago|reply
[+] [-] guruparan18|11 years ago|reply