18.2 Poker over the Telephone – Introduction to Cryptography with Coding Theory, 3rd Edition

18.2 Poker over the Telephone

Alice and Bob quickly tire of flipping coins over the telephone and decide to try poker. Bob pulls out his deck of cards, shuffles, and deals two hands, one for Alice and one for himself. Now what does he do? Alice won’t let him read the cards to her. Also, she suggests that he might not be playing with a full deck. Arguments ensue. But then someone suggests that they each choose their own cards. The betting is fast and furious. After several hundred coins (they remain unused from the coin-flipping protocol) have been wagered, Alice and Bob discover that they each have a royal flush. Each claims the other must have cheated. Fortunately, their favorite cryptologist can help.

Here is the method she suggests, in nonmathematical terms. Bob takes 52 identical boxes, puts a card in each box, and puts a lock on each one. He dumps the boxes in a bag and sends them to Alice. She chooses five boxes, puts her locks on them, and sends them back to Bob. He takes his locks off and sends the five boxes back to Alice, who takes her locks off and finds her five cards. Then she chooses five more boxes and sends them back to Bob. He takes off his locks and gets his five cards. Now suppose Alice wants to replace three cards. She puts three cards in a discard box, puts on her lock, and sends the box to Bob. She then chooses three boxes from the remaining 42 card boxes, puts on her locks, and sends them to Bob. Bob removes his locks and sends them back to Alice, who removes her locks and gets the cards. If Bob wants to replace two cards, he puts them in another discard box, puts on his lock, and sends the box to Alice. She chooses two card boxes and sends them to Bob. He removes his locks and gets his cards. They then compare hands to see who wins. We’ll assume Alice wins.

After the hand has been played, Bob wants to check that Alice put three cards in her discard box since he wants to be sure she wasn’t playing with eight cards. He puts his lock on the box and sends the box to Alice, who takes her lock off. Since Bob’s lock is still on the box, she can’t change the contents. She sends the box back to Bob, who removes the lock and finds the three cards that Alice discarded (this differs from standard poker in that Bob sees the actual cards discarded; in a standard game, Bob only sees that Alice discards three cards and doesn’t need to look at them afterward). Similarly, Alice can check that Bob discarded two cards.

Bob can check that Alice played with the hand that was dealt by asking her to send her cards to him. Alice cannot change her hand since all the remaining cards still have Bob’s locks on them (and Bob can’t open them since Alice has them in her possession).

Of course, various problems arise if Alice or Bob unjustly accuses the other of cheating. But, ignoring such complications, we see that Alice and Bob can now play poker. However, the postage for sending 52 boxes back and forth is starting to cut into Alice’s profits. So she goes back to her cryptologist and asks for a mathematical implementation. The following is the method.

Alice and Bob agree on a large prime p. Alice chooses a secret integer α with gcd(α, p1)=1, and Bob chooses a secret integer β with gcd(β, p1)=1. Alice computes α such that αα1(modp1) and Bob computes β with ββ1(modp1). A different α and β are used for each hand. A different p could be used for each hand also.

Note that cααc(modp), and similarly for β. This can be seen as follows: αα1(modp1), so αα=1+(p1)k for some integer k. Therefore, when c0(modp)

cααc(cp1)kc1kc(modp).

Trivially, we also have cααc(modp) when c0(modp).

The 52 cards are changed to 52 distinct numbers c1, , c52  modp via some prearranged scheme. Bob computes biciβ(modp) for 1i52, randomly permutes these numbers, and sends them to Alice. Alice chooses five numbers bi1, , bi5, computes bijα(modp) for 1j5, and sends these numbers to Bob. Bob takes off his lock by raising these numbers to the β power and sends them to Alice, who removes her lock by raising to the α power. This gives Alice her hand.

Alice then chooses five more of the numbers bi and sends them back to Bob, who removes his locks by raising the numbers to the β power. This gives him his hand. The rest of the game proceeds in this fashion.

It seems to be quite difficult for Alice to deduce Bob’s cards. She could guess which encrypted card bi corresponds to a fixed unencrypted card cj. This means Alice would need to solve equations of the form cjβbi(modp) for β. Doing this for the 52 choices for bi would give at most 52 choices for β. The correct exponent β could then be determined by choosing another card cj and trying the various possibilities for β to see which ones give the encrypted values that are on the list of encrypted cards. But these equations that Alice needs to solve are discrete logarithm problems, which are generally assumed to be difficult when p is large (see Chapter 10).

Example

Let’s consider a simplified game where there are only five cards: ten, jack, queen, king, ace. Each player is dealt one card. The winner is the one with the higher card. Change the cards to numbers using a=01, b=02, ,  so we have the following:

TenJackQueenKingAce2005141001031117210505141109140710305

Let the prime be p=2396271991. Alice chooses her secret α=1234567 and Bob chooses his secret β=7654321. Alice computes α=402406273 and Bob computes β=200508901. This can be done via the extended Euclidean algorithm. Just to be sure, Alice checks that αα1(modp1), and Bob does a similar calculation with β and β.

Bob now calculates (congruences are mod p)

200514β91401222410010311β15072987701721050514β7439010311091407β233799654010305β1112225809.

He shuffles these numbers and sends them to Alice:

1507298770, 1112225809, 2337996540, 914012224, 74390103.

Since Alice does not know β, it is unlikely she can deduce which card is which without a lot of computation.

Alice now chooses her card by choosing one of these numbers – for example, the fourth – raises it to the power α, and sends it to Bob:

914012224α1230896099(modp).

Bob takes off his lock by raising this to the power β and sends it back to Alice:

1230896099β1700536007(modp).

Alice now removes her lock by raising this to the power α:

1700536007α200514(modp).

Her card is therefore the ten.

Now Alice chooses Bob’s card by simply choosing one of the original cards she received – for example, 1507298770 – and sending it back to Bob. Bob computes

1507298770β10010311(modp).

Therefore, his card is the jack.

This accomplishes the desired dealing of the cards. Alice and Bob now compare cards and Bob wins. To prevent cheating, Alice and Bob then reveal their secret exponents α and β. Suppose Alice tries to claim she has the king. Bob can quickly compute α and show that the card he sent to Alice was the ten.

For another example of this game, see Example 39 in the Computer Appendices.

18.2.1 How to Cheat

No game of poker would be complete without at least the possibility of cheating. Here’s how to do it in the present situation.

Bob goes to his local number theorist, who tells him about quadratic residues. A number r(modp) is called a quadratic residue mod p if the congruence x2r(modp) has a solution; in other words, r is a square mod p. A nonresidue n is an integer such that x2n(modp) has no solution.

There is an easy way to decide whether or not a number z  0(modp) is a quadratic residue or nonresidue:

z(p1)/2+1(modp) if z is a quadratic residue1(modp) if z is a quadratic nonresidue

(see Exercise 1 ). This determination can also be done using the Legendre or Jacobi symbol plus quadratic reciprocity. See Section 3.10.

Recall that we needed gcd(α, p1)=1 and gcd(β, p1)=1. Therefore, α and β are odd. A card c is encrypted to cβ, and

(cβ)(p1)/2(c(p1)/2)βc(p1)/2(modp), 

since (±1)odd±1 (with the same choice of signs on both sides of the congruence). Therefore, c is a quadratic residue mod p if and only if cβ is a quadratic residue. The corresponding statement also applies to the α and αβ power of the cards.

When Alice sends Bob the five cards that will make up her hand, Bob quickly checks these cards to see which are quadratic residues and which are nonresidues. This means that there are two sets R and N, and for each of Alice’s cards, he knows whether the card is in R or N. This gives him a slight advantage. For example, suppose he needs to know whether or not she has the queen of hearts and he determines that it is in N. If she has only one N card, the chances are low that she has the card. In this way, Bob obtains a slight advantage and starts winning.

Alice quickly consults her local cryptologist, who fortunately knows about quadratic residues, too. Now when Alice chooses Bob’s hand, she arranges that all of his cards are in R, for example. Then she knows that his hand is chosen from 26 cards rather than 52. This is better than the partial information that Bob has and is useful enough that she gains an advantage over Bob. Finally, Alice gets very bold. She sneakily chooses the prime p so that the ace, king, queen, jack, and ten of spades are the only quadratic residues. When she chooses Bob’s hand, she gives him five nonresidues. She chooses the five residues for herself. Bob, who has been computing residues and nonresidues on each hand, has already been getting suspicious since his cards have all been residues or all been nonresidues for several hands. But now he sees before the hand is played that she has chosen a royal flush for herself. He accuses her of cheating, arguments ensue, and they go back to coin flipping.

Example

Let’s return to the simplified example. The choice of prime p was not random. In fact,

200514(p1)/21, 10010311(p1)/21, 1721050514(p1)/21, 11091407(p1)/21, 10305(p1)/21, 

so only the ace is a nonresidue, while all the remaining cards are quadratic residues.

When Alice is choosing her hand, she computes

1507298770(p1)/21.1112225809(p1)/21.2337996540(p1)/21.914012224(p1)/21.74390103(p1)/21.

This tells her that the ace is 1112225809. She raises it to the power α, then sends it to Bob. He raises it to the power β and sends it back to Alice, who raises it to the power α. Of course, she finds that her card is the ace.

For more on playing poker over the telephone, see [Fortune-Merritt].