# How the coin flipping protocol prevent Alice from generating $n$ from many primes?

This is a question from reading the paper 'Coin Flipping by Telephone - a protocol for solving impossible problems'.

The fact that the coin is unbiased is based on the fact that if n is a product of two primes, then there should be exactly four solutions to the congruence $$x^2 = f^2 \pmod n$$.

What if Alice is malicious and intentionally want to bias the result towards $$n$$ is factorizable. In that case, she could make $$n$$ a composite out of a few primes (let's say, 5), then there will be $$2^5 = 32$$ solutions and it will be highly likely that picking a solution will lead to $$n$$ turns out to factorizable?

## 2 Answers

Note that Step II of the protocol is titled "ALICE TESTS n" and this includes a method for Alice to verify that Bob chose n correctly. This appears on the third page of the paper.

$$n$$ seems to be picked by Bob or a trusted third party: As Lindell already mentioned, the n is also tested by the other party.

# Alternative

Here's an alternative protocol using non-malleable commitments:

• Alice and Bob commit to a random $$r_a, r_b \leftarrow \{0,1\}$$
• Bob additionally commits to the outcome $$c$$ they predict the coin-toss to have
• Everything is revealed, and Bob wins if $$r_a \oplus r_b = c$$

If either party is malicious they can't meaningfully influence the result since the other parties randomness is added to the final coin flip.

If every message is signed (together with some transcript hash), you could probably also prove the outcome of the run to a third party (the court).

## Optimization

The guess $$c$$ can be optimized away: since $$r_a \oplus r_b$$ is uniformly distributed, and Bob doesn't know it, there's no point in making a guess. Bob can just always guess a fixed value.

Furthermore, as Lindell mentioned in the comments, Bob doesn't need to commit to their value.

## Full Protocol

For completeness here's a full protocol:

• $$B \to A$$: nonce $$n_B$$
• $$A \to B$$: $$\{B \| n_A \| n_B \| \mathrm{Commit}(r_a)\}_{sk_A}$$
• $$B \to A$$: $$\{A \| n_A \| n_B \| r_b\}_{sk_B}$$
• $$A \to B$$: $$\{B \| n_A \| n_B \| r_a\}_{sk_A}$$

Where $$\{x\}_{sk}$$ denotes $$x \| \mathrm{Sign}_{sk}(x)$$, the plaintext and its signature under the signing key $$sk$$.

• There are much better coin tossing protocols today; Blum's protocol was the first so this is understandable. Your solution is actually problematic due to the potential malleability of the commitment. Also, not sure what "guess" there is. – Yehuda Lindell Nov 29 '20 at 10:57
• Of course, you would have to use a non-malleable commitment scheme. A simple instantiation could probably use hash functions in the ROM? The guess $c$ is the outcome that Bob predicts the coin-toss to have. – cisnjxqu Nov 29 '20 at 11:12
• I've updated my answer. – cisnjxqu Nov 29 '20 at 11:14
• The simplest protocol for a single bit is: Alice commits to a random $r_a$; Bob sends a random $r_b$ (not committed); Alice decommits and the result is $r_a \oplus r_b$. This is conceptually what Blum did, but the commitment wasn't an abstract notion then. – Yehuda Lindell Nov 29 '20 at 11:40
• I think - but I'm not sure - Blum's protocol is achieving slightly more than a coin-tossing protocol. I don't think "RIGHT PROPERTY" No. 2 on page 1 is guaranteed by the coin toss protocol you mention? Also there doesn't seem to be a notion of a "winner" in contemporary coin-toss protocols. – cisnjxqu Nov 29 '20 at 13:29