|Previous||Table of Contents||Next|
As the protocol proceeds, both Alice and Bob agree to be bound to the contract with a greater and greater probability. For example, Alice might define her a as 2 percent and Bob might define his b as 1 percent. (It would be nice if they had chosen larger increments; we will be here for a while.) Alices first message might state that she is bound with 2 percent probability. Bob might respond that he is bound with 3 percent probability. Alices next message might state that she is bound with 5 percent probability and so on, until both are bound with 100 percent probability.
If both Alice and Bob complete the protocol by the completion date, all is well. Otherwise, either party can take the contract to the judge, along with the other partys last signed message. The judge then randomly chooses a value between 0 and 1 before seeing the contract. If the value is less than the probability the other party signed, then both parties are bound. If the value is greater than the probability, then both parties are not bound. (The judge then saves the value, in case he has to rule on another matter regarding the same contract.) This is what is meant by being bound to the contract with probability p.
Thats the basic protocol, but it can have more complications. The judge can rule in the absence of one of the parties. The judges ruling either binds both or neither party; in no situation is one party bound and the other one not. Furthermore, as long as one party is willing to have a slightly higher probability of being bound than the other (no matter how small), the protocol will terminate.
Simultaneous Contract Signing without an Arbitrator (Using Cryptography)
This cryptographic protocol uses the same baby-step approach . DES is used in the description, although any symmetric algorithm will do.
Why do Alice and Bob have to go through all this work? Lets assume Alice wants to cheat and see what happens. In steps (4) and (5), Alice could disrupt the protocol by sending Bob nonsense bit strings. Bob would catch this in step (6), when he tried to decrypt whatever half he received. Bob could then stop safely, before Alice could decrypt any of Bobs message pairs.
If Alice were very clever, she could only disrupt half the protocol. She could send one half of each pair correctly, but send a gibberish string for the other half. Bob has only a 50 percent chance of receiving the correct half, so half the time Alice could cheat. However, this only works if there is one key pair. If there were only two pairs, this sort of deception would succeed 25 percent of the time. That is why n should be large. Alice has to guess correctly the outcome of n oblivious transfer protocols; she has a 1 in 2n chance of doing this. If n = 10, Alice has a 1 in 1024 chance of deceiving Bob.
Alice could also send Bob random bits in step (8). Perhaps Bob wont know that she is sending him random bits until he receives the whole key and tries to decrypt the message halves. But again, Bob has probability on his side. He has already received half of the keys, and Alice does not know which half. If n is large enough, Alice is sure to send him a nonsense bit to a key he has already received and he will know immediately that she is trying to deceive him.
Maybe Alice will just go along with step (8) until she has enough bits of the keys to mount a brute-force attack and then stop transmitting bits. DES has a 56-bit-long key. If she receives 40 of the 56 bits, she only has to try 216, or 65,536, keys in order to read the messagea task certainly within the realm of a computers capabilities. But Bob will have exactly the same number of bits of her keys (or, at worst, one bit less), so he can do the same thing. Alice has no real choice but to continue the protocol.
The basic point is that Alice has to play fairly, because the odds of fooling Bob are just too small. At the end of the protocol, both parties have n signed message pairs, any one of which is sufficient for a valid signature.
There is one way Alice can cheat; she can send Bob identical messages in Step (5). Bob cant detect this until after the protocol is finished, but he can use a transcript of the protocol to convince a judge of Alices duplicity.
There are two weaknesses with protocols of this type . First, its a problem if one of the parties has significantly more computing power than the other. If, for example, Alice can mount a brute-force attack faster than Bob can, then she can stop sending bits early in step (8), and figure out Bobs keys herself. Bob, who cannot do the same in a reasonable amount of time, will not be happy.
Second, its a problem if one of the parties stops the protocol early. If Alice abruptly stops the protocol, both face similar computational efforts, but Bob does not have any real legal recourse. If, for example, the contract specifies that she do something in a week, and Alice terminates the protocol at a point when Bob would have to spend a years worth of computing power before she is really committed, thats a problem. The real difficulty here is the lack of a near-term deadline by which the process cleanly terminates with either both or neither party bound.
These problems also apply to the protocols in Sections 5.8 and 5.9.
|Previous||Table of Contents||Next|