Alice claims that she has a method to predict the outcome of football games. She wants to sell her method to Bob. Bob asks her to prove her method works by predicting the results of the games that will be played this weekend. “No way,” says Alice. “Then you will simply make your bets and not pay me. If you want me to prove my system works, why don’t I show you my predictions for last week’s games?” Clearly there is a problem here. We’ll show how to resolve it.

Here’s the setup. Alice wants to send a bit $b$, which is either 0 or 1, to Bob. There are two requirements.

1. Bob cannot determine the value of the bit without Alice’s help.

2. Alice cannot change the bit once she sends it.

One way is for Alice to put the bit in a box, put her lock on it, and send it to Bob. When Bob wants the value of the bit, Alice removes the lock and Bob opens the box. We want to implement this mathematically in such a way that Alice and Bob do not have to be in the same room when the bit is revealed.

Here is a solution. Alice and Bob agree on a large prime $p\equiv 3(\text{mod }4)$ and a primitive root $\alpha$. Alice chooses a random number $x<p-1$ whose second bit $x_1$ is $b$. She sends $\beta \equiv {\alpha }^x(\text{mod }p)$ to Bob. We assume that Bob cannot compute discrete logs for $p$. As pointed out in the last section, this means that he cannot compute discrete logs mod 4. In particular, he cannot determine the value of $b=x_1$. When Bob wants to know the value of $b$, Alice sends him the full value of $x$, and by looking at $x\text{mod}4$, he finds $b$. Alice cannot send a value of $x$ different than the one already used, since Bob checks that $\beta \equiv {\alpha }^x(\text{mod }p)$, and this equation has a unique solution $x<p-1$.

Back to football: For each game, Alice sends $b=1$ if she predicts the home team will win, $b=0$ if she predicts it will lose. After the game has been played, Alice reveals the bit to Bob, who can see whether her predictions were correct. In this way, Bob cannot profit from the information by receiving it before the game, and Alice cannot change her predictions once the game has been played.

Bit commitment can also be accomplished with many other one-way functions. For example, Alice can take a random 100-bit string, followed by the bit $b$, followed by another 100-bit string. She applies the one-way function to this string and sends the result to Bob. After the game, she sends the full 201-bit string to Bob, who applies the one-way function and compares with what Alice originally sent.