Coin Tossing again: How to toss a coin over the phone.

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 $p$ be a Sophie German prime number i.e., $p = 2q + 1$, where $q$ is also a prime number. Examples of such primes are: $11, 23, 47, ...$. For any prime number $p$ we pick a number $a \in \{1, 2, \ldots, p-1\}$ and then look at the powers $a^j \pmod p$, where $j = 1, 2, \ldots, p-1$. For example, for $p=7$ consider the following sequence of powers for two different choices of $a$:

$a = 2: 2^1 \cong 2 \pmod 7, 2^2 \cong 4 \pmod 7, 2^3 \cong 1 \pmod 7$

$a = 3: 3^1\cong 3 \pmod 7, 3^2 \cong 2\pmod 7, 3^3 \cong 6 \pmod 7,$ $3^4 \cong 4 \pmod 7, 3^5 \cong 5 \pmod 7, 3^6 \cong 1 \pmod 7$

Note that $a=2$ gave a 'cycle', $\{2, 4, 1\}$ of length 3 while $a=3$ gave a cycle $\{3, 2, 6, 4, 5, 1\}$ of length 6. Group theory and Fermat's Little theorem tell us that the length will always divide $p-1$ and if the length is equal to $p-1$, the number $a$ is called a $\textit{primitive root}$ mod $p$. 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 $p=11$ as an example but in practice they would choose something like a 100 digit prime number. They also choose a primitive root $\alpha$ mod $p$. Remember that $p = 2q + 1$. Now we describe how Alice "tosses" the coin. Since $p = 2q + 1$ and $q$ is an odd number (it is an odd prime), the set of numbers $\{1, 2, \ldots, q\}$ can be evenly split into sets $\{1, 2, \ldots, (q-1)/2\}$ and $\{(q+3)/2, \ldots, q-1, q\}$. Note that we discarded the integer $(q+1)/2$. The two sets have the same size, namely $(q-1)/2$ and can be described as numbers either strictly less than $(q+1)/2$ or numbers strictly bigger than $(q+1)/2$.

So here is Alice's "toss". She randomly picks $x$ from one of the two sets. We label the numbers less that $(q+1)/2$ as Heads and numbers bigger than $(q+1)/2$ as Tails. Alice then computes $\alpha^x \cong \beta \pmod p$ and sends $\beta$ to Bob. This is the hidden toss.

In order to know what Alice tossed Bob would have to solve the modular equation,

$\alpha^x \cong \beta \pmod p$

for $x$. This is known to be a hard, unsolved problem (called the Discrete Logarithm Problem). Bob then calls Heads or Tails. Alice then reveals $x$ and Bob checks whether $\alpha^x \pmod p$ yields $\beta$ or not. Also, because $\alpha$ is a primitive root, Alice cannot arrange for two different values of $x$ to give the same $\beta$ (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 $p = 11$ with $\alpha = 2$. Here $q = 5$ so Alice chooses $x$ from either $\{1, 2\}$ or $\{4, 5\}$. So she tosses Heads if $\beta \in \{2^1 \cong 2, 2^2 \cong 4\}$ and Tails if $\beta \in \{2^4 \cong 5, 2^5\cong 10\}$.

If Alice choose $x = 4$, then she tossed Tails and she sends over $\beta = 5$. If Bob calls Heads, then he loses; Alice shows him $x = 4$. If Bob calls Tails he wins since Alice cannot falsify $\beta$.

So why did we pick Sophie Germain primes? The above works perfectly well for any odd number $q$ such that $2q + 1$ is a prime number. Well it turns out that this protocol is vulnerable if $p-1$ 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!