Description
Three cryptographers gather around a table for dinner. The waiter informs them that the meal has been paid by someone, who could be one of the cryptographers or the National Security Agency (NSA). The cryptographers respect each other's right to make an anonymous payment, but want to find out whether the NSA paid. So they decide to execute a two-stage protocol.
In the first stage, every two cryptographers establish a shared one-bit secret, say by tossing a coin behind a menu or by writing down a secret bit and then privately XORing it with each other participant's secret bit in turn to generate the requisite shared secrets. Suppose, after the coin tossing, cryptographer A and B share a secret bit, A and C share, and B and C share .
In the second stage, each cryptographer publicly announces a bit, which is the Exclusive OR (XOR) of the shared bits he holds if he didn't pay the meal, or the opposite of the XOR if he paid. Suppose none of the cryptographers paid, then A would announce, B would announce, and C would announce . On the other hand, if A paid, he would announce .
After the second stage is the truth revealing. One simply performs XOR of all the announced bits. If the result is 0, then it implies that none of the cryptographers paid (so NSA must have paid). Otherwise, it would imply one of the cryptographers paid, but his identity remains unknown to the other cryptographers.
The above protocol was named by David Chaum as the Dining Cryptographers network, or DC-net.
Read more about this topic: Dining Cryptographers Problem
Famous quotes containing the word description:
“The next Augustan age will dawn on the other side of the Atlantic. There will, perhaps, be a Thucydides at Boston, a Xenophon at New York, and, in time, a Virgil at Mexico, and a Newton at Peru. At last, some curious traveller from Lima will visit England and give a description of the ruins of St Paul’s, like the editions of Balbec and Palmyra.”
—Horace Walpole (1717–1797)
“It is possible—indeed possible even according to the old conception of logic—to give in advance a description of all ‘true’ logical propositions. Hence there can never be surprises in logic.”
—Ludwig Wittgenstein (1889–1951)
“The type of fig leaf which each culture employs to cover its social taboos offers a twofold description of its morality. It reveals that certain unacknowledged behavior exists and it suggests the form that such behavior takes.”
—Freda Adler (b. 1934)