Search in book...
Toggle Font Controls
Create new playlist

Name your new playlist

Playlist description (optional)
Sign In

Email address

Password

Forgot Password?

or

Continue with Facebook

Continue with Google
Sign Up

Full Name

Email address

Confirm Email Address

Password

or

Continue with Facebook

Continue with Google

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$ $p$ . Alice chooses a secret integer $α$ $α$ with $gcd (α, p - 1) = 1$ $gcd (α, p - 1) = 1$ , and Bob chooses a secret integer $β$ $β$ with $gcd (β, p - 1) = 1$ $gcd (β, p - 1) = 1$ . Alice computes $α^{'}$ $α^{'}$ such that $α α^{'} \equiv 1 (mod p - 1)$ $α α^{'} \equiv 1 (mod p - 1)$ and Bob computes $β^{'}$ $β^{'}$ with $β β^{'} \equiv 1 (mod p - 1)$ $β β^{'} \equiv 1 (mod p - 1)$ . A different $α$ $α$ and $β$ $β$ are used for each hand. A different $p$ $p$ could be used for each hand also.

Note that $c^{α α^{'}} \equiv c (mod p)$ $c^{α α^{'}} \equiv c (mod p)$ , and similarly for $β$ $β$ . This can be seen as follows: $α α^{'} \equiv 1 (mod p - 1)$ $α α^{'} \equiv 1 (mod p - 1)$ , so $α α^{'} = 1 + (p - 1) k$ $α α^{'} = 1 + (p - 1) k$ for some integer $k$ $k$ . Therefore, when $c \equiv 0 (mod p)$ $c \equiv 0 (mod p)$

c^{α α^{'}} \equiv c \cdot (c^{p - 1})^{k} \equiv c \cdot 1^{k} \equiv c (mod p) .

$c^{α α^{'}} \equiv c \cdot (c^{p - 1})^{k} \equiv c \cdot 1^{k} \equiv c (mod p) .$

Trivially, we also have $c^{α α^{'}} \equiv c (mod p)$ $c^{α α^{'}} \equiv c (mod p)$ when $c \equiv 0 (mod p)$ $c \equiv 0 (mod p)$ .

The 52 cards are changed to 52 distinct numbers $c_{1}, \dots, c_{52} m o d p$ $c_{1}, \dots, c_{52} m o d p$ via some prearranged scheme. Bob computes $b_{i} \equiv c_{i}^{β} (mod p)$ $b_{i} \equiv c_{i}^{β} (mod p)$ for $1 \leq i \leq 52$ $1 \leq i \leq 52$ , randomly permutes these numbers, and sends them to Alice. Alice chooses five numbers $b_{i_{1}}, \dots, b_{i_{5}}$ $b_{i_{1}}, \dots, b_{i_{5}}$ , computes $b_{i_{j}}^{α} (mod p)$ $b_{i_{j}}^{α} (mod p)$ for $1 \leq j \leq 5$ $1 \leq j \leq 5$ , 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 $b_{i}$ $b_{i}$ 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 $b_{i}$ $b_{i}$ corresponds to a fixed unencrypted card $c_{j}$ $c_{j}$ . This means Alice would need to solve equations of the form $c_{j}^{β} \equiv b_{i} (mod p)$ $c_{j}^{β} \equiv b_{i} (mod p)$ for $β$ $β$ . Doing this for the 52 choices for $b_{i}$ $b_{i}$ would give at most 52 choices for $β$ $β$ . The correct exponent $β$ $β$ could then be determined by choosing another card $c_{j^{'}}$ $c_{j^{'}}$ 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$ $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, \dots,$ $a = 01, b = 02, \dots,$ so we have the following:

\begin{array}{ccccc} Ten & Jack & Queen & King & Ace \\ 200514 & 10010311 & 1721050514 & 11091407 & 10305 \end{array}

$\begin{array}{ccccc} Ten & Jack & Queen & King & Ace \\ 200514 & 10010311 & 1721050514 & 11091407 & 10305 \end{array}$

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

Bob now calculates (congruences are mod $p$ $p$ )

\begin{array}{r} 200514^{β} & \equiv & 914012224 \\ 10010311^{β} & \equiv & 1507298770 \\ 1721050514^{β} & \equiv & 74390103 \\ 11091407^{β} & \equiv & 2337996540 \\ 10305^{β} & \equiv & 1112225809. \end{array}

$\begin{array}{r} 200514^{β} & \equiv & 914012224 \\ 10010311^{β} & \equiv & 1507298770 \\ 1721050514^{β} & \equiv & 74390103 \\ 11091407^{β} & \equiv & 2337996540 \\ 10305^{β} & \equiv & 1112225809. \end{array}$

He shuffles these numbers and sends them to Alice:

1507298770, 1112225809, 2337996540, 914012224, 74390103.

$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^{α} \equiv 1230896099 (mod p) .

$914012224^{α} \equiv 1230896099 (mod p) .$

Bob takes off his lock by raising this to the power $β^{'}$ $β^{'}$ and sends it back to Alice:

1230896099^{β^{'}} \equiv 1700536007 (mod p) .

$1230896099^{β^{'}} \equiv 1700536007 (mod p) .$

Alice now removes her lock by raising this to the power $α^{'}$ $α^{'}$ :

1700536007^{α^{'}} \equiv 200514 (mod p) .

$1700536007^{α^{'}} \equiv 200514 (mod p) .$

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^{β^{'}} \equiv 10010311 (mod p) .

$1507298770^{β^{'}} \equiv 10010311 (mod p) .$

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 (mod p)$ $r (mod p)$ is called a quadratic residue mod $p$ $p$ if the congruence $x^{2} \equiv r (mod p)$ $x^{2} \equiv r (mod p)$ has a solution; in other words, $r$ $r$ is a square mod $p$ $p$ . A nonresidue $n$ $n$ is an integer such that $x^{2} \equiv n (mod p)$ $x^{2} \equiv n (mod p)$ has no solution.

There is an easy way to decide whether or not a number $z \equiv 0 (mod p)$ $z \equiv 0 (mod p)$ is a quadratic residue or nonresidue:

z^{(p - 1) / 2} \equiv \{\begin{cases} + 1 (mod p) & if z is a quadratic residue \\ - 1 (mod p) & if z is a quadratic nonresidue \end{cases}

$z^{(p - 1) / 2} \equiv \{\begin{cases} + 1 (mod p) & if z is a quadratic residue \\ - 1 (mod p) & if z is a quadratic nonresidue \end{cases}$

(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 (α, p - 1) = 1$ $gcd (α, p - 1) = 1$ and $gcd (β, p - 1) = 1$ $gcd (β, p - 1) = 1$ . Therefore, $α$ $α$ and $β$ $β$ are odd. A card $c$ $c$ is encrypted to $c^{β}$ $c^{β}$ , and

(c^{β})^{(p - 1) / 2} \equiv (c^{(p - 1) / 2})^{β} \equiv c^{(p - 1) / 2} (mod p),

$(c^{β})^{(p - 1) / 2} \equiv (c^{(p - 1) / 2})^{β} \equiv c^{(p - 1) / 2} (mod p),$

since $(\pm 1)^{odd} \equiv \pm 1$ $(\pm 1)^{odd} \equiv \pm 1$ (with the same choice of signs on both sides of the congruence). Therefore, $c$ $c$ is a quadratic residue mod $p$ $p$ if and only if $c^{β}$ $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$ $R$ and $N$ $N$ , and for each of Alice’s cards, he knows whether the card is in $R$ $R$ or $N$ $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$ $N$ . If she has only one $N$ $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$ $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$ $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$ $p$ was not random. In fact,

\begin{array}{rcl} 200514^{(p - 1) / 2} & \equiv 1 \\ 10010311^{(p - 1) / 2} & \equiv 1 \\ 1721050514^{(p - 1) / 2} & \equiv 1 \\ 11091407^{(p - 1) / 2} & \equiv 1 \\ 10305^{(p - 1) / 2} & \equiv - 1, \end{array}

$\begin{array}{rcl} 200514^{(p - 1) / 2} & \equiv 1 \\ 10010311^{(p - 1) / 2} & \equiv 1 \\ 1721050514^{(p - 1) / 2} & \equiv 1 \\ 11091407^{(p - 1) / 2} & \equiv 1 \\ 10305^{(p - 1) / 2} & \equiv - 1, \end{array}$

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

When Alice is choosing her hand, she computes

\begin{array}{rcl} 1507298770^{(p - 1) / 2} & \equiv 1 \\ 1112225809^{(p - 1) / 2} & \equiv - 1 \\ 2337996540^{(p - 1) / 2} & \equiv 1 \\ 914012224^{(p - 1) / 2} & \equiv 1 \\ 74390103^{(p - 1) / 2} & \equiv 1. \end{array}

$\begin{array}{rcl} 1507298770^{(p - 1) / 2} & \equiv 1 \\ 1112225809^{(p - 1) / 2} & \equiv - 1 \\ 2337996540^{(p - 1) / 2} & \equiv 1 \\ 914012224^{(p - 1) / 2} & \equiv 1 \\ 74390103^{(p - 1) / 2} & \equiv 1. \end{array}$

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].

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.

Table of Contents for 18.2 Poker over the Telephone

Create new playlist

Sign In

Sign Up

Table of Contents for
18.2 Poker over the Telephone