Cryptography Reference
In-Depth Information
Bob follow the protocol, Alice will always receive the committed value
b
, called
the
viability property
.
Thus, bit commitment schemes are reallythe digital analogues of the use
of opaque sealed envelopes, wherein the sealing of a message in an envelope
commits the sender to the message, while keeping it secret.
The above concepts are now illustrated using an SKC to describe a bit-
commitment scheme.
Bit-Commitment Protocol Using SKC
We assume that
E
is a symmetric-key cryptosystem available to Alice and
Bob.
1. Alice generates a random bitstring
R
and sends it to Bob.
2. Bob creates a message consisting of Alice's random bitstring
R
and the
bit to which he wants to commit, producing (
R, b
) (binding). Bob uses a
random (secret symmetric) key
e
to encipher and sends the cryptogram
E
e
(
R, b
) to Alice (concealing).
3. When readyto reveal his commitment, Bob sends the key
e
to Alice.
4. Alice deciphers the message via
E
−
e
(
E
e
(
R, b
)) = (
R, b
) to reveal the bit
and the random bitstring to verifythe bit's validit.
The next scheme involves the DLP.
Coin Flipping by Telephone Using Discrete Logs
Suppose that the problem with which Alice and Bob are faced is the deter-
mination of who gets the car after the divorce, discussed on the previous page.
The problem is to be solved using a coin flip in the following manner.
Protocol Steps
:
1. Alice and Bob agree upon a large prime
p
such that the factorization of
p
−
1 is known.
∈
F
p
and sends both to Bob.
2. Alice selects two generators
α, β
)
∗
, then he computes exactly
3. Bob chooses a random integer
x
∈
(
Z
/
(
p
−
1)
Z
α
x
(mod
p
)or
y
β
x
(mod
p
), which he sends to Alice.
one of
y
≡
≡
4. Alice guesses whether
y
is a function of
α
or
β
and sends the guess to Bob.
5. If Alice's guess is correct, the result of the flip is deemed to be
heads
, and
if it is incorrect, it is deemed to be
tails
. Bob sends the result of the coin
flip to Alice.
6. Bob reveals
x
to Alice. Then Alice computes
α
x
(mod
p
) and
β
x
(mod
p
)
to verifyboth outcomes of the coin tosses.
Search WWH ::
Custom Search