Cryptography Reference
In-Depth Information
h
(Alice's bid) = 2F9A5
Alice
Bob
h
(Bob's bid) = C1558
Alice's bid
h
(Alice's bid)
= 2F9A5 ??
Bob's bid
h
(Bob's bid)
= C1558 ??
Figure 6.4.
Use of a hash function for cryptographic commitments
A solution is for each party to determine their bid and then exchange a
commitment
ahead of time. They can then reveal their bids at leisure. The process,
which is illustrated in Figure 6.4, runs as follows:
1. Alice determines her bid and then hashes it. This is her commitment. She sends
the hash of her bid (but not the bid itself) to Bob. Bob stores the hash of Alice's
bid.
2. Bob determines his bid and then hashes it. This is his commitment. He sends
the hash of his bid (but not the bid itself) to Alice. Alice stores the hash of Bob's
bid. The bidding stage is now closed.
3. Alice sends her bid to Bob. Bob computes the hash of Alice's bid and checks
that it matches the hash that Alice sent in step 1. If it matches then he accepts
Alice's bid as genuine.
4. Bob sends his bid to Alice. Alice computes the hash of Bob's bid and checks
that it matches the hash that Alice sent in step 2. If it matches then she accepts
Bob's bid as genuine.
5. Both parties are now aware of the two bids and accept them. The companies
are now free, if they want, to accept the lower bid.
In any application involving the use of a hash function to provide commitments,
the main security concern that arises is whether any of the parties could 'get out'
of their commitment by some means. The way to get out of a commitment is to
find an alternative input that hashes to the same commitment. In terms of the
above application, this provides a cheating party with an option to select either of
the inputs depending on the situation that unfolds during the bidding protocol.
If Bob can find two bids with the same commitment then he can wait for Alice to
reveal her bid and then strategically make a decision. He could choose a low-value
input in order to win the contract (if it is lower than Alice's bid) or he could even
wriggle out of the process by deliberately losing through submitting a higher bid
