Mental poker
Encyclopedia
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 stems from the card game
poker
which is one of the games to which this kind of problem applies. A similar problem is flipping a coin over a distance.
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).
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 you decrypt 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 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 A6 to A10. Bob decrypts his cards by using both Alice's keys and his own for these cards, B6 to B10. Bob can now see the cards. Alice cannot know which cards Bob has because she does not have access to Bob's keys B6 to B10 which are required to decrypt the cards.
s: 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.
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 proof
s, so that players don't need to reveal their strategy to verify the game's correctness.
The C++ library libtmcg [STA05] (available at http://www.nongnu.org/libtmcg/) 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.
The card-generation algorithm requires a cryptosystem with two key properties. The encryption E must be additively homomorphic, so that E(c1)E(c2) = E(c1 + c2). Second, collisions must be detectable, without revealing the plaintext. In other words, given E(c1) and E(c2), it must be possible to answer whether c1=c2, without the players learning any other information (specifically, the identities of c1 and c2). The Elgamal encryption
scheme is just one example of a well-known system with these properties.
The algorithm operates as follows:
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
, the sum 
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.
The basic protocol using two servers is as follows:
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.
Trusted third party
In cryptography, a trusted third party is an entity which facilitates interactions between two parties who both trust the third party; The Third Party reviews all critical transaction communications between the parties, based on the ease of creating fraudulent digital content. In TTP models, the...
. The term is also applied to the theories surrounding these problems and their possible solutions. The name stems from the card game
Card game
A card game is any game using playing cards as the primary device with which the game is played, be they traditional or game-specific. Countless card games exist, including families of related games...
poker
Poker
Poker is a family of card games that share betting rules and usually hand rankings. Poker games differ in how the cards are dealt, how hands may be formed, whether the high or low hand wins the pot in a showdown , limits on bet sizes, and how many rounds of betting are allowed.In most modern poker...
which is one of the games to which this kind of problem applies. A similar problem is flipping a coin over a distance.
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
Mail
Mail, or post, is a system for transporting letters and other tangible objects: written documents, typically enclosed in envelopes, and also small packages are delivered to destinations around the world. Anything sent through the postal system is called mail or post.In principle, a postal service...
, for instance), this suddenly becomes very difficult. And for electronic card games, such as online poker
Online poker
Online poker is the game of poker played over the Internet. It has been partly responsible for a dramatic increase in the number of poker players worldwide...
, 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
Adi Shamir
Adi Shamir is an Israeli cryptographer. He is a co-inventor of the RSA algorithm , a co-inventor of the Feige–Fiat–Shamir identification scheme , one of the inventors of differential cryptanalysis and has made numerous contributions to the fields of cryptography and computer...
, Ron Rivest
Ron Rivest
Ronald Linn Rivest is a cryptographer. He is the Andrew and Erna Viterbi Professor of Computer Science at MIT's Department of Electrical Engineering and Computer Science and a member of MIT's Computer Science and Artificial Intelligence Laboratory...
and Len Adleman (the creators of the RSA-encryption protocol).
Shuffling cards using commutative encryptionEncryptionIn cryptography, encryption is the process of transforming information using an algorithm to make it unreadable to anyone except those possessing special knowledge, usually referred to as a key. The result of the process is encrypted information...
One possible algorithmAlgorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
for shuffling
Shuffle
Shuffling is a procedure used to randomize a deck of playing cards to provide an element of chance in card games. Shuffling is often followed by a cut, to help ensure that the shuffler has not manipulated the outcome.-Shuffling techniques:...
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 you decrypt this data will not matter.
Example: Alice
Alice and Bob
The names Alice and Bob are commonly used placeholder names for archetypal characters in fields such as cryptography and physics. The names are used for convenience; for example, "Alice sends a message to Bob encrypted with his public key" is easier to follow than "Party A sends a message to Party...
has a plaintext
Plaintext
In cryptography, plaintext is information a sender wishes to transmit to a receiver. Cleartext is often used as a synonym. Before the computer era, plaintext most commonly meant message text in the language of the communicating parties....
message. She encrypts this, producing a garbled ciphertext
Ciphertext
In cryptography, ciphertext is the result of encryption performed on plaintext using an algorithm, called a cipher. Ciphertext is also known as encrypted or encoded information because it contains a form of the original plaintext that is unreadable by a human or computer without the proper cipher...
which she gives then to Bob
Alice and Bob
The names Alice and Bob are commonly used placeholder names for archetypal characters in fields such as cryptography and physics. The names are used for convenience; for example, "Alice sends a message to Bob encrypted with his public key" is easier to follow than "Party A sends a message to Party...
. Bob encrypts the ciphertext again, using the same scheme as Alice but with another key
Key (cryptography)
In cryptography, a key is a piece of information that determines the functional output of a cryptographic algorithm or cipher. Without a key, the algorithm would produce no useful result. In encryption, a key specifies the particular transformation of plaintext into ciphertext, or vice versa...
. 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:- Alice and Bob agree on a certain "deck" of cards. In practice, this means they agree on a set of numbers or other data that each element of the set represents a card.
- Alice picks an encryption key A and uses this to encrypt each card of the deck.
- Alice shuffles the cards.
- Alice passes the encrypted and shuffled deck to Bob. With the encryption in place, Bob cannot know which card is which.
- Bob picks an encryption key B and uses this to encrypt each card of the encrypted and shuffled deck.
- Bob shuffles the deck.
- Bob passes the double encrypted and shuffled deck back to Alice.
- 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.
- Alice picks one encryption key for each card (A1, A2, etc) and encrypts them individually.
- Alice passes the deck to Bob.
- 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.
- Bob picks one encryption key for each card (B1, B2, etc) and encrypts them individually.
- Bob passes the deck back to Alice.
- 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
Alice and Bob
The names Alice and Bob are commonly used placeholder names for archetypal characters in fields such as cryptography and physics. The names are used for convenience; for example, "Alice sends a message to Bob encrypted with his public key" is easier to follow than "Party A sends a message to Party...
, Dave
Alice and Bob
The names Alice and Bob are commonly used placeholder names for archetypal characters in fields such as cryptography and physics. The names are used for convenience; for example, "Alice sends a message to Bob encrypted with his public key" is easier to follow than "Party A sends a message to Party...
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 A6 to A10. Bob decrypts his cards by using both Alice's keys and his own for these cards, B6 to B10. Bob can now see the cards. Alice cannot know which cards Bob has because she does not have access to Bob's keys B6 to B10 which are required to decrypt the cards.
Weakness
The encryption scheme used must be secure against known-plaintext attackKnown-plaintext attack
The known-plaintext attack is an attack model for cryptanalysis where the attacker has samples of both the plaintext , and its encrypted version . These can be used to reveal further secret information such as secret keys and code books...
s: 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
One-time pad
In cryptography, the one-time pad is a type of encryption, which has been proven to be impossible to crack if used correctly. Each bit or character from the plaintext is encrypted by a modular addition with a bit or character from a secret random key of the same length as the plaintext, resulting...
, 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 [SCH98]. The work is concerned with general-purpose operations (masking and unmasking cards, shuffling and re-shuffling, inserting a card in to a stack, etc.) that make the protocols applicable to any card game. The cryptographic protocolsCryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
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 proof
Zero-knowledge proof
In cryptography, a zero-knowledge proof or zero-knowledge protocol is an interactive method for one party to prove to another that a statement is true, without revealing anything other than the veracity of the statement....
s, so that players don't need to reveal their strategy to verify the game's correctness.
The C++ library libtmcg [STA05] (available at http://www.nongnu.org/libtmcg/) 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) don't 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(c1)E(c2) = E(c1 + c2). Second, collisions must be detectable, without revealing the plaintext. In other words, given E(c1) and E(c2), it must be possible to answer whether c1=c2, without the players learning any other information (specifically, the identities of c1 and c2). The Elgamal encryption
ElGamal encryption
In cryptography, the ElGamal encryption system is an asymmetric key encryption algorithm for public-key cryptography which is based on the Diffie–Hellman key exchange. It was described by Taher Elgamal in 1984. ElGamal encryption is used in the free GNU Privacy Guard software, recent versions of...
scheme is just one example of a well-known system with these properties.
The algorithm operates as follows:
- Players initialize an empty list L that records cards that are in use.
- To deal a card, each player computes a random number ri in {0,...,51}, computes E(ri), and publishes a non-malleable commitmentCommitment schemeIn cryptography, a commitment scheme allows one to commit to a value while keeping it hidden, with the ability to reveal the committed value later. Commitments are used to bind a party to a value so that they cannot adapt to other messages in order to gain some kind of inappropriate advantage...
to E(ri) - Players then publish their actual E(ri), and can verify that every player honors its commitment
- Players compute
, which produces a new encrypted card E(r*), with 
- 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
Mix network
Digital mixes were invented by David Chaum in 1981. Digital mixes create hard-to-trace communications by using a chain of proxy servers. Each message is encrypted to each proxy using public key cryptography; the resulting encryption is layered like a Russian doll with the message as the...
.
Note that the random number generation
Pseudorandomness
A pseudorandom process is a process that appears to be random but is not. Pseudorandom sequences typically exhibit statistical randomness while being generated by an entirely deterministic causal process...
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
, the sum 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:
- Servers S1 and S2 encrypt and shuffle a deck of cards, and publish a non-malleable commitment to some permutationPermutationIn mathematics, the notion of permutation is used with several slightly different meanings, all related to the act of permuting objects or values. Informally, a permutation of a set of objects is an arrangement of those objects into a particular order...
of encrypted cards to the players. This can be done with any of several well-understood cryptographic protocols. - Players compute independent random numbers in {0,...,51}, which are combined to generate a random number in {0,..., 51}, as in [GOL05]
- 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
Online poker
Online poker is the game of poker played over the Internet. It has been partly responsible for a dramatic increase in the number of poker players worldwide...
. 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.