Dining cryptographers protocol

From Wikipedia, the free encyclopedia

The dining cryptographers protocol is a method of anonymous communication. It offers untraceability of both the sender and the recipient.

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 adjacent cryptographers from the rest. Every cryptographer picks a random number in private and shows it to the cryptographer to his right. Then each cryptographer computes the difference between his own number and the number he was shown by his neighbour to the left, adding a message if he wants to transmit one. He publicly announces the result. All cryptographers then add up the published numbers. If the sum is 0, no one sent a message. If the sum is a valid message, one cryptographer transmitted a message. If the sum is invalid, more than one cryptographer tried to transmit a message; they wait a random time and try again.

Recipient anonymity is simple: Everybody receives the message at the same time, so the message could be meant for anybody. Sender anonymity holds because no person knows the number of the person to his right. Therefore, for each person (other than himself) it appears to him to be equally likely that he is the one who added the message.

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.

See also: cryptography

Compare: dining philosophers problem