Cryptography Reference
In-Depth Information
access to a reverse phone directory or phone CD-ROM that offered
the chance to look up a listing by the number, not the name.
The solution to using a one-way function to flip a coin over a
distance is simple:
1. You choose
is a
one-way hash function that is easy to compute but practically
impossible to invert.
x
, a random number and send me
h
(
x
)
where
h
2. I can't figure out
x
from the
h
(
x
)
thatyousentme.SoIjustguess
x
whether
is odd or even. This guess is sent back to you.
3. If I guess correctly about whether
is odd or even, then the coin
flip will be tails. If I'm wrong, then it is heads. You determine
whether it is heads or tails and send
x
x
back to me.
4. I compute
)
to check that you're not lying. You can only
cheatifitiseasyforyoutofindtwonumbers,
h
(
x
x
, which is odd,
and
)
. No one knows how to
do this for good one-way hash functions.
y
, which is even, so that
h
(
x
)=
h
(
y
The protocol can be
made stronger if I
provide the first
n
bits of
This is the algorithm that the two neighbors can use to flip their
coins without sitting next to each other at the dinner table. If you
find yourself arguing with a friend over which movie to attend, you
can use this algorithm with a phone book for the one-way function.
Then the flip will be fair.
The second tool must allow for everyone to reveal at the same
time whether their coin flips agree or disagree. Chaum's paper sug-
gests allowing people to broadcast their answers simultaneously but
on different frequencies. This requires more sophisticated electron-
ics than computer networks currently have. A better solution is to re-
quirepeopletocommittotheiranswersthrougha
bit commitment
protocol.
The solution is pretty simple. First, the entire group agrees on a
stock phrase or a collection of bits. This should be determined as
late as possible to prevent someone from trying to use computation
in advance to game the system. Call this random set of bits
x
. A precomputed set of
x
and
y
can't be used.
B
.To
announce their answers, the
n
participants at the table:
1. Choose
n
random keys,
{
k
1
,...,k
n
}
,insecret.
2. Individually take their answers, put
in front of the answer,
and encrypt the string with their secret key. This is
B
f
k
i
(
Ba
i
)
,
where
f
is the encryption function,
k
i
is the key, and
a
i
is the
answer to be broadcast.
