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

a=2:212(mod7),224(mod7),231(mod7)a = 2: 2^1 \cong 2 \pmod 7, 2^2 \cong 4 \pmod 7, 2^3 \cong 1 \pmod 7

a=3:313(mod7),322(mod7),336(mod7),a = 3: 3^1\cong 3 \pmod 7, 3^2 \cong 2\pmod 7, 3^3 \cong 6 \pmod 7, 344(mod7),355(mod7),361(mod7)3^4 \cong 4 \pmod 7, 3^5 \cong 5 \pmod 7, 3^6 \cong 1 \pmod 7

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

So here is Alice's "toss". She randomly picks xx from one of the two sets. We label the numbers less that (q+1)/2(q+1)/2 as Heads and numbers bigger than (q+1)/2(q+1)/2 as Tails. Alice then computes αxβ(modp)\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,

αxβ(modp)\alpha^x \cong \beta \pmod p

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

If Alice choose x=4x = 4, then she tossed Tails and she sends over β=5\beta = 5. If Bob calls Heads, then he loses; Alice shows him x=4x = 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 qq such that 2q+12q + 1 is a prime number. Well it turns out that this protocol is vulnerable if p1p-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!

Note by Krishnan Shankar
4 years, 5 months ago

No vote yet
1 vote

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Sort by:

Top Newest

This is known to be a hard, unsolved problem (called the Discrete Logarithm Problem).

This is false; in fact, this is one of the very few problems not known to be either in P or NP-complete (in other words: not known whether it is easy, hard, or neither).

Ivan Koswara - 4 years, 5 months ago

Log in to reply

It is hard in that all known algorithms are exponential or sub-exponential. It is unsolved in the sense that it is not known whether it is NP complete. Same as factoring. So we can argue semantics or look at the bigger picture i.e., it provides, along with factoring and elliptic curves, our best algorithms in use every single day for nearly all communication, encryption and security.

Krishnan Shankar - 4 years, 5 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...