Suppose Alice and Bob live in different cities and have inherited their uncle's old Volkswagen Beetle. Instead of trying to sell it they decide to "flip a coin" for it over the phone. How can they ensure a fair coin toss? In this note we introduce some ideas from modern day cryptography that allow such a toss. Let's lay out the parameters for such a toss.
We are going to say that Alice tosses and Bob calls Heads or Tails. We need to make sure that: (i) Alice presents her toss to Bob without showing it to him. This is called "bit commitment". (ii) Bob definitively calls Heads or Tails. (iii) After Alice reveals the actual toss, Bob must be able to verify that it is indeed Alice's toss and that she could not cheat.
We do all this using modular arithmetic. Let be a Sophie German prime number i.e., , where is also a prime number. Examples of such primes are: . For any prime number we pick a number and then look at the powers , where . For example, for consider the following sequence of powers for two different choices of :
Note that gave a 'cycle', of length 3 while gave a cycle of length 6. Group theory and Fermat's Little theorem tell us that the length will always divide and if the length is equal to , the number is called a mod . So in the example above, 3 is a primitive root mod 7, but 2 is not a primitive root mod 7.
Back to Alice and Bob. What is their protocol over the phone? First they pick a prime number that is a Sophie Germain prime. We will use as an example but in practice they would choose something like a 100 digit prime number. They also choose a primitive root mod . Remember that . Now we describe how Alice "tosses" the coin. Since and is an odd number (it is an odd prime), the set of numbers can be evenly split into sets and . Note that we discarded the integer . The two sets have the same size, namely and can be described as numbers either strictly less than or numbers strictly bigger than .
So here is Alice's "toss". She randomly picks from one of the two sets. We label the numbers less that as Heads and numbers bigger than as Tails. Alice then computes and sends to Bob. This is the hidden toss.
In order to know what Alice tossed Bob would have to solve the modular equation,
for . This is known to be a hard, unsolved problem (called the Discrete Logarithm Problem). Bob then calls Heads or Tails. Alice then reveals and Bob checks whether yields or not. Also, because is a primitive root, Alice cannot arrange for two different values of to give the same (this is a simple corollary of group theory). So Alice cannot have cheated. And Bob cannot cheat at least not in a short amount of time since the Discrete Logarithm problem is computationally infeasible for large primes.
Here it is in action: Alice and Bob pick with . Here so Alice chooses from either or . So she tosses Heads if and Tails if .
If Alice choose , then she tossed Tails and she sends over . If Bob calls Heads, then he loses; Alice shows him . If Bob calls Tails he wins since Alice cannot falsify .
So why did we pick Sophie Germain primes? The above works perfectly well for any odd number such that is a prime number. Well it turns out that this protocol is vulnerable if has lots of small prime factors to something called the Pohlig-Hellman algorithm (another note perhaps). Picking a Sophie Germain prime makes this protocol just that much stronger.
So go forth and toss and be secure!