Cryptography Reference
In-Depth Information
(see Chapter 10) can cut off the path back to its source, but they can
often be compromised or traced. Practically any message on the Net
can be traced because packets always flow fromone place to another.
This is generally completely impractical, but it is still possible.
None of these methods offers unconditional security, but there
is one class of algorithms created by David Chaum that will make
it impossible for anyone to detect the source of a message. He ti-
tled the system the “dining cryptographers” which is a reference to
a famous problem in computer system design known as the “dining
philosophers.” In the Dining Philosophers problem,
n
philosophers
chopsticks set up so there is one chopstick
between each pair. To eat, a philosopher must grab both chopsticks.
If there is no agreement and no schedule, then no one will eat at all.
Chaum phrased the problem as a question of principle. Three
cryptographers are eating dinner and is from the National Security
Agency. The waiter arrives and tells them that one person at the ta-
ble has already arranged for the check to be paid, but he wouldn't
say who left the cash. The cryptographers struggle with the problem
because neither of the two nongovernment employees want to ac-
cept even an anonymous gratuity from the NSA. But, because they
respect the need for anonymity, they arrange to solve the problem
with a coin-tossing algorithm. When it is done, no one will know
who paid the check, but they'll know if the payer is from the NSA.
This framing story is a bit strained, but it serves the purpose. In
the abstract, one member will send a 1-bit message to the rest of
thetable. Everyonewillbeabletogetthesamemessage,butno
onewillbeabletoidentifywhichpersonatthetablesentit.There
are many other situations that seem to lend themselves to the same
problem. For instance, a father might return home to find the rear
window smashed. He suspects that it was one of the three kids, but
it could have been a burglar. He realizes that none will admit to
doing it. Before calling the police and reporting a robbery, he uses
the same dining cryptographer protocol so one of the kids can admit
to breaking the window without volunteering for punishment.
1
If a 1-bit message can be sent this way, then there is no reason
why long messages cannot come through the same channel. One
problem is that no one knows when someone else is about to speak,
since no one knows who is talking. The best solution is to never in-
terrupt someone else. When a free slot of time appears, participants
should wait a random amount of time before beginning. When they
sit around the table with
n
Random protocols for
sharing a
communication
channel are used by the
Ethernet developed at
Xerox PARC.
start broadcasting something, they should watch for corrupted mes-
1
This may be progressive parenting, but I do not recommend that you try this at
home. Don't let your children learn to lie this well.
