Question

This question is on coin flips. Recall that this is done as follows. Alice picks two primes p, q and n = p · q. Bob sends to Alice x^2 mod n for some random x. Recall that there are some 4 solutions +a, −a, +b, −b, with either a or b equaling x. Alice sends to Bob either a or b. Say for example that x = a. If Bob gets b he can factor n so he wins but if he gets a he can not factor n so Alice wins.

1. Say that Alice cheats and uses p = q. Show that Bob always loses in the coin flip

2. What should Bob ask Alice after some games he loses (and starts to suspect) to reveal so he can prove Alice as a cheater?

Answer 1

1. If Alice chooses the same prime, then the 4 solutions all correspond to the factor x and hence whatever number Alice sends to Bob, Bob can't factor the number (This is because all are quadratic residues of x and when the primes were different one of them corresponded to x, and the other to one of the primes. If both the primes are the same, then the prime information gets erased in favour of the number Bob randomly chooses).

2. Bob should just ask Alice to send the number of distinct primes she is using. Since it will be 1, she's caught.