By Sung-Ming Yen

Cryptographic games -- flipping coin (ÂY»ÉªO) & playing poker over a network!?

[This article is suitable for beginners with a few knowledge of the RSA cryptosystem.]

Playing multi-user game over a network is interesting. However, playing poker or flipping a coin (ÂY»ÉªO) over a network much more cooooooooooool!

The following material (with some editing by the author) was originally prepared by Marc Joye within an email to the author.

Below are the rules to flip a coin between two persons over Internet.

Here is the situation: M. Joye and S.-M. Yen have written a paper which has to be presented at a conference. Who will present the paper? To be fair, Joye and Yen decide to "flip a coin". Unfortunately they cannot meet together. So they will play over the Internet by email. Is it really fair? Yes, if cryptographic techniques are used.

The idea behind coin flipping over Internet is quite simple: one-wayness. A one-way function is a function h such that computing h(x) for some x is easy, but such that the inverse computation, namely computing x given h(x) is "impossible". Here "impossible" has to be understood as computationally infeasible. For example, what are the prime factors of n=391? Hmmmmmm let me think... So you see that this is not so easy. However, the inverse problem is easy: what is the product of 17 and 23... and then after a few seconds you answer 391. The factorization problem is the basis of the RSA. But for cryptographic purposes the number n must be chosen as the product of two primes of at least 256 bits (=77 digits) --with a little bit more time, I'm sure you can find that 391=17*23, or at least you pocket calculator will!-- In that case with the best known methods of factorization, it would take more than the age of the Universe to find the two prime factors of n. We will use the RSA problem as underlying one-way function. More explicitly, the one-way function will be h(x) = x^3 mod n where n is the product of two large prime factors.

This is interesting but how to flip a coin? Be patient... here are the rules. Suppose that Joye flips the coin. He first chooses two large random prime numbers p and q and computes their product n=p*q. (p and q are the secrets of Joye, chuuuuuut!). The conventions are

(Since there are the same proportion of odd and even numbers this sounds good.) Now Joye chooses a number m between 1 and n, that is, he flips the coin. Remind that if m is odd then this means that the coin shows "head", and if m is even then it shows "tail". Joye then computes c=h(m) and sends c and n to Yen. Now Yen has to guess the parity of m (that is, to guess if m is odd or even); or in other words Yen has to guess if the coin, already flipped by Joye, shows the head or the tail. If he finds the right parity, he wins; otherwise he looses. Let r denote the choice of Yen. Yen then sends r to Joye, and upon receiving r, Joye sends his original choice of m and the secret factors p and q. Joye and Yen can now check who is the winner by comparing r with m mod 2 (i.e., the parity of m). And of course Yen must check that 1<m<n and that c=h(m).

To sum up:

In the following there is an example. Note that the parameters have been chosen artificially very small so that you can play with them on your pocket calculator. In the emails they exchanged, Joye and Yen played with 512-bit numbers!

(1) Initialization

Joye selects two secret primes p and q and computes their product n=2836921.

(2) Coin flipping

Joye randomly selects m (1< m < n): m = 1692704.
Choosing m means flipping the coin: so the coin shows tail (chuuuuuuut secret) because m is even.

(3) First email

Joye computes c = m^3 mod n = 2539740.
(Take your calculator and verify the computations!)
Joye sends c and n to Yen.

(4) Tail or head?

Now, it is the hard time for Yen to guess "0" (tail) or "1" (head).

(5) Second email

OK, Yen finally guesses "r=1" (head) and sends the result to Joye.

(6) Third email

Joye sends an email to Yen to let him know he looses:-( To prove it, he sends the value of m=1692704 together with the prime factors p and q.

(7) Winner?

Yen checks that he effectively looses the game by computing 1692704 mod 2 = 0 and comparing it with his choice r (=1). He also performs the appropriate verifications.

Questions/Exercises

1. In the above example, why in Step (2) Joye must choose m greater than 142?
   
2. Using your result in 1., show that from the only knowledge of c=2685619, Yen can find that the coin shows "head".
3. Give the minimal value for m (as a function of n) in the general case so that this failure does not occur.
4. Why Joye must send p and q in Step (6)?
5. Upon receiving c and n (Step (4)), Yen can try to factor n. Do you know the two prime factors of 2836921?
   [Hint: Try to write n as a difference of 2 squares. So if n = a^2 - b^2, then you find p=(a-b) and q=(a+b).]
6. Prove that in the suggested method of factorization (due to Fermat), a is always greater than the square root of n. Prove also that a square is always congruent 0 or 1 modulo 4.
7. Using point 5., write down the Fermat's algorithm of factorization.
8. [Hard] In the previous protocol, Joye and Yen exchanged 3 emails to flip the coin. Is it possible to flip a coin by exchanging only 2 emails?
9. Using ideas presented here, how is it possible to roll a dice over the Internet? To play poker?
10. How to extend that games to more than 2 players?