Alice is living in Anchorage and Bob is living in Baltimore. A friend, not realizing that they are no longer together, leaves them a car in his will. How do they decide who gets the car? Bob phones Alice and says he’ll flip a coin. Alice chooses “Tails” but Bob says “Sorry, it was Heads.” So Bob gets the car.
For some reason, Alice suspects Bob might not have been honest. (Actually, he told the truth; as soon as she called tails, he pulled out his specially made two-headed penny so he wouldn’t have to lie.) She resolves that the next time this happens, she’ll use a different method. So she goes to her local cryptologist, who suggests the following method.
Alice chooses two large random primes and , both congruent to 3 mod 4. She keeps them secret but sends the product to Bob. Then Bob chooses a random integer and computes . He keeps secret but sends to Alice. Alice knows that has a square root mod (if it doesn’t, her calculations will reveal this fact, in which case she accuses Bob of cheating), so she uses her knowledge of and to find the four square roots of (see Section 3.9). One of these will be , but she doesn’t know which one. She chooses one at random (this is the “flip”), say , and sends it to Bob. If , Bob tells Alice that she wins. If , Bob wins.
But, asks Alice, how can I be sure Bob doesn’t cheat? If Alice sends to Bob and , then Bob knows all four square roots of , so he can factor . In particular, gives a nontrivial factor of . Therefore, if it is computationally infeasible to factor , the only way Bob could produce the factors and would be when his value of is not plus or minus the value of that Alice sends. If Alice sends Bob , Bob has no more information than he had when Alice sent him the number . Therefore, he should not be able to produce and in this case. So Alice can check that Bob didn’t cheat by asking Bob for the factorization of .
What if Alice tries to cheat by sending Bob a random number rather than a square root of ? This would surely prevent Bob from factoring . Bob can guard against this by checking that the square of the number Alice sends is congruent to .
Suppose Alice tries to deceive Bob by sending a product of three primes. Of course, Bob could ask Alice for the factorization of at the end of the game; if Alice produces two factors, they can be quickly checked for primality. But Bob shouldn’t worry about this possibility. When is the product of three distinct primes, there are eight square roots of . Therefore, up to sign there are four choices of numbers for Alice to send. Each of the three wrong choices will allow Bob to find a nontrivial factor of . So Alice would decrease her chances of winning to only one in four. Therefore, she should not try this.
There is one flaw in this procedure. Suppose Bob decides he wants to lose. He can then claim his value of was exactly the value that Alice sent him. Alice cannot dispute this since the only information she has is the square of Bob’s number, which is congruent to the square of her number. There are other procedures that can prevent Bob from trying to lose, but we will not discuss them here.
Finally, we should mention that it is not difficult to find primes and that are congruent to 3 mod 4. The density of primes congruent to 1 mod 4 is the same as the density of primes that are 3 mod 4. Therefore, find a random prime . If it is not 3 mod 4, try another. This process should succeed quickly. We can find similarly.
Alice chooses
She sends
to Bob. Bob takes
(this isn’t as random as it looks; but Bob thinks the decimal expansions of square roots look random) and computes
which he sends to Alice.
Alice computes
Therefore, she knows that
The Chinese remainder theorem puts these together in four ways to yield
Suppose Alice sends 1012103737618676889 to Bob. This is , so Bob declares Alice the winner.
Suppose instead that Alice sends 937850352623334103 to Bob. Then Bob claims victory. By computing
he can prove that he won.