in fundamentals 2,017 Words

Poker is hard, especially for cryptographers

I have this friend who’s an obsessive poker fan, to the point where it’s actually a little scary. The worst part is that as a computer scientist, he approaches the game with a numeracy that would make an Apollo 11 technician blush. He refuses to touch a hand until he’s computed the precise odds, which wouldn’t be so bad if he didn’t tell me about it — all while gibbering mysterious 19th-century words like ‘flop’ and ‘river’ and ‘hole card’.

When this happens I try to smile and nod like I have some idea what he’s talking about. But trust me, I don’t. My card-playing experience runs to a few tense games of ‘Go Fish!’ and a drunken weekend in Vegas playing Blackjack.

Still, there’s one aspect of card playing that I am fascinated by: mental poker. This is a blanket term for a protocol that allows mutually-distrustful people to deal and play cards without a dealer, or, indeed, any trusted party at all.

Like all crypto/privacy protocols, mental poker interests me because it’s so counterintuitive. You get a bunch of people together, none of whom trust each other — some of whom may be actively trying to cheat the others — and at the end of the day everyone gets a fair deal, or at worst, enough warning to get out clean.

I also love the concept because it’s so obviously disruptive. In case you hadn’t heard, US law enforcement doesn’t have warm, cuddly feelings towards online poker. This past spring, the FBI took down three of the biggest sites, and there’s no reason to think they’re done. I may not be a poker player myself, but decentralized mental poker appeals to me, mostly because it would be a lot harder to shut down — especially if it was tied to a peer-to-peer currency such as Bitcoin. (On the other hand, you’d be playing for Bitcoin. So there’s that.)

In the rest of this post I’m going to talk a little bit about where mental poker came from and how it works. I don’t plan to give too many equations, but it will get a little (or a lot) wonky, and will certainly depart a bit from the pro-implementer, pro-engineering spirit of this blog. (If you want to pass, I certainly won’t hold it against you.)

Secret history

Like every other problem in our field, ‘Mental poker’ was first proposed by Shamir, Rivest and Adleman (note to self: invent new research field, get dibs on all the interesting problems.) Their motivation was — well, let’s just let them tell it:

Once there were two “mental chess” experts who had become tired of their favorite pastime. Let’s play “mental poker” for some variety suggested one. “Sure” said the other. “Just let me deal!”

In that first paper, Shamir et al. managed the fascinating trick of both proving that mental poker is impossible, and then giving a protocol to do it securely. (Don’t get discouraged by this — it happens.)

While the Shamir et al. paper may have been the first to address mental poker, it definitely wasn’t the last. Indeed, it’s an open secret that most of the ‘fundamental’ advances in cryptography — semantically-secure encryption, zero-knowledge proofs, etc. — were actually just happy accidents: things that dropped out while MIT cryptographers were fiendishly seeking better ways to play Five Card Stud with their colleagues at Weizmann.

Whether you believe this or not, the fact is that mental poker is really challenging, and did motivate a lot of new work. To explain this, let’s go over the basics of the problem.

Face up or Face Down?

For a mental poker scheme to be useful, it has to achieve three basic goals:

  1. The shuffle must be random.
  2. The deck must be correct — no trick aces!
  3. Some cards must be dealt face down.

Let’s focus on the last point for a moment. If you’ve ever toyed with the idea of writing a card game, you probably know how to represent face-up cards: just let each be an integer from 0 through 51. Obviously we’ll need a table to map those values into something that humans can work with, but fundamentally this is no sweat.

Face-down cards, on the other hand, are more complicated. We need a publicly-visible data structure that can do what a physical card does: it must commit the holder to a particular face value. At the same time, it must hide that value from everyone else.

The simple and elegant solution (in case you didn’t see it coming) is to encrypt the face-down cards using a semantically-secure encryption scheme such as Elgamal.

(A quick note: ‘semantic security’ is a fundamental security definition that’s considered the minimum bar for every modern encryption scheme. In english, it means that you can’t learn any useful information from a ciphertext. It goes without saying that the definition was proposed in a paper about mental poker.)

While encryption solves some of our problems, it doesn’t quite solve them all. In fact, it gives us a big new one. If we’re going to encrypt the cards, who the heck is going to hold the decryption key?

And this is where modern public-key cryptography really shines. A basic trick is that every player can generate a ‘share’ of the decryption key such that the sum of all those shares is the decryption key for the entire scheme (they can also use these shares to generate the public key). This allows the players to cooperatively decrypt any ciphertext, such that no individual player ever gets the entire decryption key.

And now we have almost enough to describe a ‘simple’ mental poker protocol.

Generate the deck. First, one player generates an ordered ‘deck’ of cards — the integers (0, 1, 2, 3, …, 51) — and encrypts each one using known randomness. Since this player might be a cheater, she publishes all of her work so the group can repeat and verify it. If all goes well, the group should be confident that the deck is well-formed, i.e., there are no missing cards or duplicates.

Shuffle. The players now pass the deck around the ‘table’, giving each individual a chance to shuffle it thoroughly. This is harder than it sounds; it’s not enough to simply permute the order of the encrypted cards, since the ciphertexts themselves are recognizable (think of each card as having a different back-face). The good news is that schemes like Elgamal allow you to re-randomize a ciphertext — change its outward appearance without changing the underlying plaintext.

Unfortunately, re-randomizing ciphertexts leads to yet another serious limitation: if the output of the shuffle can’t be linked to the input, then a malicious player could simply replace the cards instead of shuffling them. The last player to shuffle would essentially be deciding the order (and even the types of cards in) the deck!

Fortunately, in their quest for better ways to play poker, cryptographers have solved this this problem as well. The answer is something called a publicly-verifiable shuffle (used in Mix networks, which completely by accident were later shown to have applications in e-Voting and anonymous communication). In these systems, the shuffler can actually prove that the shuffled deck contains the same cards, without giving away the shuffle.

Dealing. If everything’s gone well, and if at least one player is honest, the players should now have a beautifully shuffled deck of encrypted cards. It remains only to deal them. To do this, the players cooperatively decrypt the cards using their key shares. If the card is face-up, they go ‘all the way’ and simply reveal the plaintext to the whole group. If it’s face-down, they collaborate most of the way, but let the recipient handle the last component of the decryption process.

Ok, maybe this wasn’t so simple. And there’s still a lot I’m leaving out — including the whole Mix mechanism and a bunch of zero-knowledge proofs you’d need to prevent cheating in the decryption process. Still, figuring that stuff out isn’t the problem.

The problem is that the protocol above is expensive.

A single shuffle alone can result in megabytes of data, which every party has to verify. So much for playing mental poker over the phone (or, to use a modern analogy, Twitter). Clearly a better approach is needed.

Golle to the rescue?

The problem with the ‘classic’ approach is that it requires the players to generate and shuffle an entire deck of cards every time they play. But this is pointless work, since many games don’t actually use the entire deck. A better approach would generate random cards on the fly, then check for ‘collisions’: cards that have already been dealt to the players.

This is what Philippe Golle proposed back in 2005, in a paper submitted to the ITCC e-Gaming track (What is this? It sounds awesome.) I know about this paper because a student recently implemented it in Charm; hence I can attest to the fact that it’s practical. Actually, it cooks.

Golle’s idea was to use the additively-homomorphic property of schemes such as Elgamal,* to allow the parties to draw random cards. In a nutshell, each of the k players selects a random value r in the range 0 to 51, then encrypts her value and publishes it to the other players. The group can now add the ciphertexts together, which gives them the encryption of (r_1 + r_2 + … + r_k).

By working together the group can decrypt the summed ciphertext, which reveals a plaintext in the range 0 to (k*51). By reducing this modulo 52 they obtain a random card number.

The big obstacle to this approach is that you can get repeated cards, i.e., collisions. The clever part of Golle’s protocol is the way that he checks that a given card hasn’t been dealt to a player already, which allows him to ‘throw back’ any colliding cards.

I won’t spend much time on how this works, except to point out that Golle’s paper may have a small bug (though one that’s easily fixed). To make a long story short, when a collision occurs in the first round of dealing — i.e., a card is dealt that already exists in a player’s hand — Golle will actually ‘throw back’ both the new card, and the card that was already in the player’s hand.

Why am I complaining about this? Well, imagine that a real poker dealer did this. That is, he paused, asked to look at your hand, took away the King of Hearts and put it back in the deck (with a brief apology for his mistake). It strikes me that this would not be viewed as kosher. I’ll leave it to a real poker player to tell me what the implications are, but I’m trusting they’re not good.

All the rest

This has been a long post, and while I hope it’s given some of the flavor of the problem, obviously there’s still tons I haven’t said.

For example, how do you check for winning conditions? How do you handle players who ‘drop out’ when the cards don’t go their way? And finally, how would you tie the result of the game to a Bitcoin ‘pot’? (Bitcoin script seems like a great candidate for this, but unfortunately it’s not well supported on the actual Bitcoin network.)

And of course, none of this addresses the real problem with online poker, which mere cryptography does not solve — namely, how to keep your opponents from sharing their hands via a backchannel.

Still, this is a fun area that I’d love to see pursued with a bit more vigor. Yes, from time to time someone promises to do it, but those promises never quite materialize. So if you’re a poker fan and you find this stuff interesting, please do drop me a line.

Notes:

* For the super-wonky, Elgamal is actually multiplicatively homomorphic, but that’s ok. What’s being encrypted is g^r, for some generator g. The product of (g^r1 * g^r2 = g^{r1+r2}) which can be decrypted by testing the result against a table of pre-computed values. (This only works for small values).

12 thoughts on “Poker is hard, especially for cryptographers”

  2. Are there any card games that game theoretically incentivize sharing with teammates and disincentivize sharing with opponents? Perhaps poker isn't the best choice for distributed card games.

  3. Hey there. Found this post to be interesting idea. I have thought about a similar idea in the past, and it was, how could you make a console (PS3), with a real poker games on it. This presents a similar problem, even though you have a computer being the “dealer”. That's because, how do you conceal your hand, while making it fully visible on a tv screen?

    Have not really came up with a full answer, except that, there is 1326 possible starting hands. The reason I bring this up, is that it presents a way of dealing cards to players, and shuffling is reduced to being a pairing of 2 cards to a number between 1-1236. So lets say, I pick 1000 as my number before we start playing. Each hand, 1000 would pair up to a different 2 cards set by a trustworthy dealer.

    Since I have not really contemplated the idea of mental poker to the same extent, it seems reasonable that there might be ways to verify your number through (for example) zero knowledge proofs with other players? Then your question becomes, how does one fairly shuffle (by producing a card-number pair I spoke of above) the cards without a dealer? This I think also maybe solvable, with some type of encryption/hash like your talking about, where each player can potentially verify.

    Best of luck, would be interested in your thoughts.

  5. You can get rid of the backchannel by playing all games heads-up (ie., with only two players).

  6. I really like your idea of heads up matches. I would only be confused about split pots, if your being technical to the rules of poker. But heads up is probably a great approach to solve that problem.

    I also wanted to clarify this a bit. In short, it seems like most “mental” poker games can go by this simple rule. If there are any face down, non-community cards every player must pick a number as a choice before the game begins. That player then proceeds the rest of the game based on that pre-game irreversible decision.

  8. One primitive that may improve the efficiency of the protocol is using exponential Elgamal where the (multiplicative) order of the group formed by the exponents is 52. For example, encrypting messages r of the form g^h^r where g generates Gq, h generates Z_52, and r is an integer [0,…,51]. This allows a *partially* homomorphic (e.g., a ciphertext + a plaintext -> ciphertext) modular addition.

    It is used here (originates in second citation but explained more clearly in first):

    * “Parallel Shuffling and its Application to Pret a Voter” (Section 2.2)
    * “Verifiable Rotation of Homomorphic Encryptions” (Section 3.1)

    The idea would be to generate a card, a ciphertext of 0 is passed to the first participant (P1) who exponentiates in a value h^r, rerandomizes, and proves it is of correct form. The second participant takes P1's output and repeats. Because the message will always remain mod 52, this improves a few steps in the poker protocol:

    1) The reduction mod 52 step (proof and verification) can be eliminated
    2) The collision-testing step can be simplified. You can do a plaintext equality test on any two ciphertexts directly (instead of checking against the set S from the paper)

    However it may exhibit the following drawback:

    1) The proof of correct form may be less efficient. Since anyone can take the current ciphertext and exponentiate by the 52 values h^0…h^52, it suffices for Pi to prove their output is a rerandomization of one of those 52 values (which can be done with a large “DISPEP” proof). Golle's trick of whittling this down to 6 DISPEP proofs may / may not apply.

  9. I love playing poker as well. My friend taught me how to play it. Playing poker includes luck and strategies. You need to be very vigilant to the way your opponent acts. As the name implies, you also need to show some poker face to at least give a signal to your contenders that you've got a better set of cards.

    Poker Tips

  10. I am also a poker enthusiasts and I can say that playing poker is not really a game of luck, of course special skills is needed in order to learn how to play poker and play like a pro. Being aggressive and observant is the best characteristics that a player must be to win the game.

Comments are closed.