Mental poker

Mental poker is the common name for a set of cryptographic problems that concerns playing a fair game over distance without the need for a trusted third party. The term is also applied to the theories surrounding these problems and their possible solutions. The name comes from the card game poker which is one of the games to which this kind of problem applies. Similar problems described as two party games are Blum's flipping a coin over a distance, Yao's Millionaires' Problem, and Rabin's oblivious transfer.

The problem can be described thus: "How can one allow only authorized actors to have access to certain information while not using a trusted arbiter?" (Eliminating the trusted third-party avoids the problem of trying to determine whether the third party can be trusted or not, and may also reduce the resources required.)

In poker, this could translate to: "How can we make sure no player is stacking the deck or peeking at other players' cards when we are shuffling the deck ourselves?". In a physical card game, this would be relatively simple if the players were sitting face to face and observing each other, at least if the possibility of conventional cheating can be ruled out. However, if the players are not sitting at the same location but instead are at widely separate locations and pass the entire deck between them (using the postal mail, for instance), this suddenly becomes very difficult. And for electronic card games, such as online poker, where the mechanics of the game are hidden from the user, this is impossible unless the method used is such that it cannot allow any party to cheat by manipulating or inappropriately observing the electronic "deck".

Several protocols for doing this have been suggested, the first by Adi Shamir, Ron Rivest and Len Adleman (the creators of the RSA-encryption protocol). This protocol was the first example of two parties conducting secure computation rather than secure message transmission, employing cryptography; later on due to leaking partial information in the original protocol, this led to the definition of semantic security by Shafi Goldwasser and Silvio Micali. The concept of multi-player mental poker was introduced in Moti Yung's 1984 book Cryptoprotocols. The area has later evolved into what is known as secure multi-party computation protocols (for two parties, and multi parties as well).

Shuffling cards using commutative encryption

One possible algorithm for shuffling cards without the use of a trusted third party is to use a commutative encryption scheme. A commutative scheme means that if some data is encrypted more than once, the order in which one decrypts this data will not matter.

Example: Alice has a plaintext message. She encrypts this, producing a garbled ciphertext which she gives then to Bob. Bob encrypts the ciphertext again, using the same scheme as Alice but with another key. When decrypting this double encrypted message, if the encryption scheme is commutative, it will not matter who decrypts first.

The algorithm

An algorithm for shuffling cards using commutative encryption would be as follows:

1. Alice and Bob agree on a certain "deck" of cards. In practice, this means they agree on a set of numbers or other data such that each element of the set represents a card.
2. Alice picks an encryption key A and uses this to encrypt each card of the deck.
3. Alice shuffles the cards.
4. Alice passes the encrypted and shuffled deck to Bob. With the encryption in place, Bob cannot know which card is which.
5. Bob picks an encryption key B and uses this to encrypt each card of the encrypted and shuffled deck.
6. Bob shuffles the deck.
7. Bob passes the double encrypted and shuffled deck back to Alice.
8. Alice decrypts each card using her key A. This still leaves Bob's encryption in place though so she cannot know which card is which.
9. Alice picks one encryption key for each card (A₁, A₂, etc.) and encrypts them individually.
10. Alice passes the deck to Bob.
11. Bob decrypts each card using his key B. This still leaves Alice's individual encryption in place though so he cannot know which card is which.
12. Bob picks one encryption key for each card (B₁, B₂, etc.) and encrypts them individually.
13. Bob passes the deck back to Alice.
14. Alice publishes the deck for everyone playing (in this case only Alice and Bob, see below on expansion though).

The deck is now shuffled.

This algorithm may be expanded for an arbitrary number of players. Players Carol, Dave and so forth need only repeat steps 2-4 and 8-10.

During the game, Alice and Bob will pick cards from the deck, identified in which order they are placed in the shuffled deck. When either player wants to see their cards, they will request the corresponding keys from the other player. That player, upon checking that the requesting player is indeed entitled to look at the cards, passes the individual keys for those cards to the other player. The check is to ensure that the player does not try to request keys for cards that do not belong to that player.

Example: Alice has picked cards 1 to 5 in the shuffled deck. Bob has picked cards 6 to 10. Bob requests to look at his allotted cards. Alice agrees that Bob is entitled to look at cards 6 to 10 and gives him her individual card keys A₆ to A₁₀. Bob decrypts his cards by using both Alice's keys and his own for these cards, B₆ to B₁₀. Bob can now see the cards. Alice cannot know which cards Bob has because she does not have access to Bob's keys B₆ to B₁₀ which are required to decrypt the cards.

Weakness

The encryption scheme used must be secure against known-plaintext attacks: Bob must not be able to determine Alice's original key A (or enough of it to allow him to decrypt any cards he does not hold) based on his knowledge of the unencrypted values of the cards he has drawn. This rules out some obvious commutative encryption schemes, such as simply XORing each card with the key. (Using a separate key for each card even in the initial exchange, which would otherwise make this scheme secure, doesn't work since the cards are shuffled before they're returned.)

Depending on the deck agreed upon, this algorithm may be weak. When encrypting data, certain properties of this data may be preserved from the plaintext to the ciphertext. This may be used to "tag" certain cards. Therefore, the parties must agree on a deck where no cards have properties that are preserved during encryption.

"A Toolbox for Mental Card Games" and its implementation

Christian Schindelhauer describes sophisticated protocols to both perform and verify a large number of useful operations on cards and stacks of cards in his 1998 paper "A Toolbox for Mental Card Games" [SCH98]. The work is concerned with general-purpose operations (masking and unmasking cards, shuffling and re-shuffling, inserting a card into a stack, etc.) that make the protocols applicable to any card game. The cryptographic protocols used by Schindelhauer are based on quadratic residuosity, and the general scheme is similar in spirit to the above protocol. The correctness of operations can be checked by using zero-knowledge proofs, so that players do not need to reveal their strategy to verify the game's correctness.

The C++ library libtmcg [STA05] provides an implementation of the Schindelhauer toolbox. It has been used to implement a secure version of the German card game Skat, achieving modest real-world performance. The game Skat is played by three players with a 32-card deck, and so is substantially less computationally intensive than a poker game in which anywhere from five to eight players use a full 52-card deck.

A non-shuffling poker protocol

To date, mental poker approaches based on the standard Alice-Bob protocol (above) do not offer high enough performance for real-time online play. The requirement that each player encrypts each card imposes a substantial overhead. A recent paper by Golle [GOL05] describes a mental poker protocol that achieves significantly higher performance by exploiting the properties of the poker game to move away from the encrypt-shuffle model. Rather than shuffle the cards and then deal as needed, with the new approach, the players generate (encrypted) random numbers on the fly, which are used to select the next card. Every new card needs to be checked against all the cards that have already been dealt to detect duplicates. As a result, this method is uniquely useful in poker-style games, in which the number of cards dealt is very small compared to the size of the whole deck. However, the method needs all cards that have already been dealt to be known to all, which in most poker-style games would beat its very purpose.

The card-generation algorithm requires a cryptosystem with two key properties. The encryption E must be additively homomorphic, so that E(c₁)*E(c₂) = E(c₁ + c₂). Second, collisions must be detectable, without revealing the plaintext. In other words, given E(c₁) and E(c₂), it must be possible to answer whether c₁=c₂, without the players learning any other information (specifically, the identities of c₁ and c₂). The Elgamal encryption scheme is just one example of a well-known system with these properties. The algorithm operates as follows:

1. Players initialize an empty list L that records cards that are in use.
2. To deal a card, each player computes a random number r_i in {0,...,51}, computes E(r_i), and publishes a non-malleable commitment to E(r_i)
3. Players then publish their actual E(r_i), and can verify that every player honors its commitment
4. Players compute [math]\displaystyle{ \Pi E(r_i) = E(\Sigma r_i) }[/math], which produces a new encrypted card E(r*), with [math]\displaystyle{ r* = \Sigma r_i }[/math]
5. Players check if E(r*) is already in L. If not, E(r*) is dealt to the appropriate player, and added to L. When cards need to be revealed, they can be jointly decrypted.

In this way, the players need only to compute encryption for the cards that are actually used in the game, plus some overhead for the collisions that is small as long as the number of cards needed is much less than the size of the deck. As a result, this scheme turns out to be 2-4 times faster (as measured by the total number of modular exponentiations) than the best-known protocol [JAK99] that does full shuffling using mix-networks.

Note that the random number generation is secure as long as any one player is generating valid random numbers. Even if k-1 players collude to generate the number r*, as long as the kth player truthfully generates a random [math]\displaystyle{ r' }[/math], the sum [math]\displaystyle{ r = r* + r' }[/math] is still uniformly random in {0, 51}.

Measured in terms of the number of single-agent encryptions, the algorithm in [GOL05] is optimal when no collisions occur, in the sense that any protocol that is fair to every player must perform at least as many encryption operations. At minimum, every agent must encrypt every card that is actually used. Otherwise, if any agent doesn't participate in the encryption, then that agent is susceptible to being cheated by a coalition of the remaining players. Unknown to the non-encrypting agent, the other agents may share the keys to enable them all to know the values of all the cards. Thus, any approach relying on the agents to perform the encryption must focus on schemes that minimize the effect of collisions if they are to achieve better performance.

Better performance through increased trust

Any mental poker protocol that relies on the players to perform the encryption is bound by the requirement that every player encrypt every card that is dealt. However, by making limited assumptions about the trustworthiness of third parties, significantly more efficient protocols may be realized. The protocol for choosing cards without shuffling may be adapted so that the encryption is handled by two or more servers. Under the assumption that the servers are non-colluding, such a protocol is secure.

The basic protocol using two servers is as follows:

1. Servers S1 and S2 encrypt and shuffle a deck of cards, and publish a non-malleable commitment to some permutation of encrypted cards to the players. This can be done with any of several well-understood cryptographic protocols.
2. Players compute independent random numbers in {0,...,51}, which are combined to generate a random number in {0,..., 51}, as in [GOL05]
3. The random number is used as an index into the random permutation, the appropriate player gains "ownership" of the specified card, and the servers send that player the keys to read the card's value.

In this protocol, servers S1 and S2 must collude if either is to learn the values of any cards. Furthermore, because players ultimately decide which cards are dealt, non-trustworthy servers are unable to influence the game to the extent that is possible in traditional online poker. The scheme may be extended to allow more servers, (and thus, increased security), simply by including the additional servers in the initial encryption. Finally, step one in the protocol may be done offline, allowing for large numbers of shuffled, encrypted "decks" to be pre-computed and cached, resulting in excellent in-game performance.

References

• Goldwasser, S. and Micali, S. 1982. Probabilistic encryption & how to play mental poker keeping secret all partial information. In Proceedings of the Fourteenth Annual ACM Symposium on theory of Computing.
• [STA05] Stamer, H. Efficient Electronic Gambling: An Extended Implementation of the Toolbox for Mental Card Games. WEWoRC 2005, LN P-74, 1-12, 2005
• [SCH98] Schindelhauer, C. A Toolbox for Mental Card Games. Tech. Rep. of Medizinische Universitat Lubeck.
• [GOL05] Golle, P. Dealing Cards in Poker Games. In Proceedings of the International Conference on Information Technology: Coding and Computing, (2005)

External links

• A bibliography on mental poker
• LibTMCG - C++ library for creating secure and fair online card games
• Dealing Cards with Cryptography - A Numberphile video with Ron Rivest explaining the intuition behind the Mental Poker paper.