Cryptography Reference
In-Depth Information
differences, which is even so no message is sent. In the third case, a
message is sent. That is, a “1” or an “on” goes through. The same is
true for the fourth and sixth cases.
The examples don't need to be limited to three people. Any num-
ber is possible and the systemwill still work out the same. Each coin
flipped is added into the final count twice, once for the owner and
once for the neighbor. So the total number of differences will only be
odd if one person is changing the answer.
What happens if two people begin to send at once? The protocol
fails because the two changes will cancel each other out. The total
number of differences will end up even again. If three people try to
send at once, then there will be success because there will be an odd
number of changes. A user can easily detect if the protocol is failing.
You try to broadcast a bit, but the final answer computed by everyone
is the absence of a bit. If each person trying to broadcast stops and
waits a random number of turns before beginning again, then the
odds are that they won't collide again.
Is this system unconditionally secure? Imagine you're one of the
people at the table. Everyone is flipping coins and it is clear that there
is some message emerging. If you're not sending it, then can you
determine who is? Let's say that your coin comes up heads. Here's a
table with some possible outcomes:
You Diner #2 Diner #3
Coin Match Coin Match Coin Match
HY HN? Y
HY
HN
HY
HY HN
T Y
HY HY ? N
HY
HY
T N
HY HY
HN
HNT Y ? Y
HN
T Y
HY
HNT Y
T Y
HNT N? N
HN
T N
T N
HNT N
HN
There are four possible scenarios reported here.
In each case,
We were never that
concerned about
Slothrop
qua
Slothrop.
—Thomas Pynchon in
Gravity's Rainbow
your coin shows heads. You get to look at the coin of Diner #2 to your
right. There are an odd number of differences appearing in each case
so someone is sending a message. Can you tell who it is?
The first entry for each scenario in the table has a question mark
for the flip of the third diner's coin. You don't know what that coin is.
