Dining cryptographers protocol

The dining cryptographers protocol is a method of anonymous communication. It allows for any member of a group to multicast data to every other member of the group. Though the broadcast is public, the protocol guarantees that its sender remains anonymous. This protocol allows only for one member of the group to transmit data during any given round.

The method is as follows: three or more cryptographers (nodes) arrange themselves around a circular dinner table (ring network), with menus (encrypted links) hiding the interaction of each pair of cryptographers. Each cryptographer secretly writes down a bit (zero or one) and shows it to every other cryptographer. Then, each cryptographer computes the xors of their own number and each of the other cryptographers' numbers. That is, if the bit the cryptographer is shown is the same as theirs the result is 'zero', and if they are different the result is 'one'. Every cryptographer that does not want to send a message reports their result. The cryptographer that does want to send a message reports the opposite of their result. All cryptographers then add up the published numbers. If the sum is an even number, no one sent a message. If odd, a one-bit message was sent.

Sender anonymity holds because no person knows what comparison value another person reported. Therefore, noone knows who reported the opposite comparison value - the sender. This does not hold in case of two cryptographers - if one person does not transmit a message but a message is being broadcast, he obviously knows who sent it.

History

Originally, the problem was described so that cryptographers would only compare their bit with the person to their right, and make that comparison public. However, this provides the possibility of the group colluding to find out who is sending the message. If collusion is not a problem, this method requires many less comparisons ($2n$ vs $n^{2}$).

Security considerations

Advantages

• Anonymous sender
• Anonymous recipient (if key used)

• Allows key to be sent in main channel rather than key channel

Disadvantages

• $n^{2}$ bytes transfer for one byte in case of peer to peer communication where n is number of participants. As mentioned above, this can be reduced to $2n$ if there is no possibility of collusion between participants, but in many cases even this lower bound is intractable.
• Malicious party can inject random bits to corrupt the message. Chaum present trap messages can prevent malicious data.

See also

• cryptography
• The Dining Cryptographers Protocol/Rewrite
• Dining cryptographers problem
• onion routing

External links

• "Dining cryptographers protocol" at Cryptodox