Coin Flipping by Telephone. Poker Revisited

In some cryptographic protocols it is required that the parties, perhaps located far apart, generate together a random sequence, without the assistance of a trusted referee. If the number of parties is two, this amounts to flipping a coin by telephone. Clearly, A and B cannot do this in the simple way that one of them tosses a coin and tells the result over the telephone to the other. Absolute honesty would then be required. On the other hand, if one of the parties is accompanied by a trusted referee, coin tossing presents no problems.

A wellknown illustration of the situation, due to M. Blum, is the following. A{lice) and B(ob) have just divorced and live in different cities. They want to decide who gets the car by flipping a coin. No suitable referee is available. The goal A and B want to achieve can be depicted also using the following model of flipping a coin in a well.

A and B stand far apart from each other. B is standing by a deep well with very clear water. When A tosses a coin into the well (hopefully not missing it!) then B knows the outcome of the flip but is unable to change it. On the other hand, A does not know the outcome. Thus, B just tells A what the outcome is. The outcome is possibly used for some purpose. Later on A may come and look into the well to check whether or not the information given by B was correct. Basically it does not matter whether A or B flips the coin into the well. However, the model described above is intended to capture the essence of flipping a coin by telephone. This is hardly feasible if only one of the parties is active.

The following protocol shows how A flips a coin to B by telephone. At first only B knows the outcome and tells it to A. (The outcome might determine the instructions for a certain part of a more extensive protocol.) Later on A may check that the information given by B about the outcome was correct.

Step 1: A chooses two large primes p and q and tells their product n = pq to B.

Step 2: B chooses a random number m from the interval (1, n/2) and tells A the square z = (u², mod n).

Step 3: A computes ± x and ± y, the four square roots of z (mod n). This is possible because A knows the factorization of n. Let x' be the smaller of the numbers (x, mod n) and ( — x, mod ri). Let / be defined similarly from ± y. Observe that u = x' or u = y'.

Step 4: A guesses whether u = x' or u = y'. More specifically, A finds the smallest number i such that the i-th bit of x' differs from the i-th bit of y' and tells B one of the two guesses "the i-th bit in your number u is 0" or "the i-th bit in your number u is 1".

Step 5: B tells A whether the guess was correct (heads) or wrong (tails).

Step 6: Later B lets A come "near the well" by telling the number u.

Step 7: A releases the factorization of n.

Clearly, A has no way of knowing u and, hence the guess is a real one. If B could cheat by changing the number u after /I's guess, then he would be in the possession of both x' and y and, hence, could factorize n by computing the greatest common divisor of x' — / and n. Also to avoid this, A tells only one bit of her guess in Step 4, rather than telling the entire x' or /.

The protocol relies on the assumption that factoring is difficult. Indeed, one can say that most of the theory of cryptographic protocols is dangerously dependent on the difficulty of this single problem.

Many protocols have been presented for coin flipping by telephone. The following is a general scheme. A and B both know a (supposedly) one-way function /but not the inverse f~^x.B chooses a random number x and tells A the value/(x). A makes a guess about some 50-50 property of the number x. (For instance: Is x even or odd?) B tells A whether or not the guess was correct. Later on, B tells A the number x.

The following protocol is somewhat different from the protocol above, al­though it is based on similar ideas and assumptions. It uses some number-theoretic facts concerning the Jacobi symbol (see Appendix B). Assume that n = pq as before. Consider numbers a such that 0 < a < n and (a, n) = 1. Exactly half of such numbers a satisfy (- ) = 1 and, again, exactly half of the numbers satisfying the

\n j

latter condition are quadratic residues (mod n). The value of the Jacobi symbol is easily computable. Whether or not a is a quadratic residue (mod n) can be easily computed only if p and q are known.

The protocol runs as follows. B chooses p and q and tells A their product n, as

well as a random number a such that = 1. A guesses whether or not a is

a quadratic residue (mod n). B tells A whether or not the guess was correct. Later on, B lets A "come near the well" by disclosing p and q.

Here it is essential that A checks that the disclosed p and q are indeed primes. (This observation is due to Juha Honkala.) Otherwise, B could cheat as follows. To start with, B chooses three primes p,, p₂, q^ and a number a such that

- (r)—-

Assume that /l's right guess is interpreted as "heads" and her wrong guess as "tails".

If B wants "heads", he proceeds as follows. If A says "residue", B discloses p = p_lp₂ and q = qi- If A says "nonresidue", B discloses p = p_l and q = p₂qi-

If B wants "tails", he proceeds as follows. If A says "residue", B discloses p = p₁, q = p₂qj. If A says "nonresidue", B discloses p = p_xp₂, <? = <?,-

Coin flipping can be naturally extended to the case, where A flips a number x to B. This means flipping x bit by bit. After the process B knows x but A knows only the number of bits in x.

The idea of flipping a number can be applied to obtain a safer protocol, [GM], for playing poker by telephone. The 52 cards are represented as 6-bit numbers. Any polynomial-time algorithm for guessing with at least 51% probability a specific bit of the opponent's card can be rewritten as a random polynomial-time algorithm for factoring n = pq. The protocol makes use of the number-theoretic fact that

- ) = — (- | whenever a and b are different square roots of the same number nj \nj

(mod n) and, moreover, p = q = 3 (mod 4). ("Different" means here that a # ± fc (mod «).) We now give a brief description of the protocol.

For i = 1,. . . , 52, A chooses two large primes p_i and q_t satisfying p_f = q_t = 3 (mod 4) and computes their product n_l = p_cq_t. She shuffles her pack and associates the number n, to the /-th card in the shuffled pack. The i-th card is represented as

a 6-tuple (t^ t₂,... , t₆), where each tj is a random number with = 1 and,

moreover, tj is a quadratic residue (mod n,) exactly in case the j'-th bit in the binary representation of the i-th card equals 1. A tells B all of the 52 6-tuples together with the numbers n_t (but does not tell p, and q_t).

B shuffles his pack, constructs and tells A an analogous representation of his cards, using large primes r, and s_t and their products m„ for i = 1,..., 52.

To deal one card to B, A flips 52 numbers x, to B. Thus, B knows x, for i = 1,.. ., 52, but A does not know any of the numbers x, at the moment. B tells

A the numbers (xf, mod together with except for one particular value

i = kB tells A the numbers (xf, mod n_k) and — ^j. A can compute square roots

because she knows the factorization of n_f. A now tells B the particular square root of xf whose Jacobi symbol was given her by B. Observe that A has no way of knowing the particular value i = k. But for this value, B has obtained sufficient information to factor n_k. Indeed, B knows two different square roots of the same number (mod n_k). Therefore, B can decrypt the fc-th card in ,4's pack. This will be one of his cards. For values i ^ kB has received no additional information. Finally, B removes the card dealt to him from his own pack and informs A which card was removed. A is not able to decrypt this information and, thus, cannot tell what the removed card was.

B now deals to A one card from his pack following the same procedure. Since there are only 51 cards left in fl's pack, he flips only 51 numbers to A. The procedure is continued until five cards have been dealt to both participants. (The procedure is readily modified to the customary variants of draw poker.) After the game all secret information is released. It is easy to see how eventual cheating will be found out at this stage. For instance, it will be found out if a participant has taken more than one card in one step, although temporarily it is possible to announce more than one exceptional Jacobi symbol. Considering all the details about flipping numbers, working with quadratic residues, etc., the protocol is altogether very complicated.

Date: 2015-02-16; view: 764