Dining cryptographers protocol

related topics
{math, number, function}
{system, computer, user}
{law, state, case}
{work, book, publish}
{day, year, event}

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, no one 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.

Contents

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 fewer comparisons (2n vs n2).

Security considerations

Advantages

  • Anonymous sender
  • Anonymous recipient (if key used)
  • Allows key to be sent in main channel rather than key channel

Disadvantages

  • n2 bytes transfer for one bit 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

External links

Full article ▸

related documents
Entropy encoding
XPointer
Filter (Unix)
Sequential access
SAX
RIPEMD
Binary symmetric channel
Data element
Common Language Infrastructure
Poem code
Cfront
Common Language Runtime
RC5
Canonical Encoding Rules
XBasic
Escape character
Name server
Small-C
Yacc
Euler-Jacobi pseudoprime
Landau's function
Simple module
Star height problem
Elementary event
Location parameter
Typed link
Metcalfe's law
Abbreviated Test Language for All Systems
Bit error ratio
Pedal triangle