A Cryptographic Protocol invented by David Chaum in 1988, first published in his paper "The Dining Cryptographers Problem: Unconditional Sender and Recipient Untraceability" in the Journal of Cyptography

Imagine the following scenario:

Three cryptographers are out for dinner one night. When they sit down for dinner they notice that their favorite NSA agent is also sitting in the restaurant. After eating their meal they ask for the bill, only to be told that some has paid for them, but the waiter can't tell them who.

The crytographers then start to wonder who paid for them, was it one of their three or was it the NSA agent? The problem here is that, if one of the crytographers had paid then he isn't going to want the other two to know about it, so the solution is to find a protocol that allows for one person to disclose knowlage of something without anyone else knowing that it was that person who disclosed it.

So they use a protocol that, as the title of the paper suggests, allows for sender untraceability. It works like this:

1) Each person takes and unbiased coin and tosses it.

2) They then place the coin so only him (or her...) and the person on his right can see the result of the toss.

3) Each person then announces the values of the coins that he can see - but with out saying which side which coin is on. So they'll just state if they can see two heads, a head and a tail or two tails. The trick is that the cryptographer that paid for the meal (if it was indeed one of the cryptographers that paid and not the NSA agent) will lie about the value of the one of the coins that he can see.

4) The total number of heads and tails is tallied. If there is an odd number of each then each cryptographer knows that one of themselves paid for the meal, else, if the numbers were even, the NSA paid (how nice of them...)

This is perhaps better demonstrated in pictoral format.

This is a birds-eye view of the table just after the coins have been tossed:

       H
      / \
    1/   \2
    /     \
   T-------H
       3

If none of the cryptographers had paided for the meal then they would give the following results:

1: HT
2: HH
3: TH

If you tally these then you see that there are four Heads and two Tails announced, an even number of both.

If, however, number 2 had paid then the annouced results would be different, instead you would get:

1: HT
2: HT
3: TH

As you can see, in this case there are three Heads and three Tails, so one of the cyptographers has lied about the values of the coins that he can see. The trick here is that, since each person can only see a part of the information available, it is impossible to tell which person lied.

This same protocol can also be used to transmit messages. Say that an odd number of heads or tails counts for a binary 1 and an even number for a 0. As long as the crytographers continue to toss their coins, one of their party can anonymously transmit a message bit-by-bit by alternatly lying and not lying to construct their message in binary.

For more information about this protocol the original paper is available from http://komarios.net/crypt/diningcr.htm

For more information about crytographic protocols in general I personaly recommend "Applied Cryptography" by Bruce Schneier.

Log in or register to write something here or to contact authors.