Mental poker
   HOME

TheInfoList



OR:

Mental poker is the common name for a set of
cryptographic Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or '' -logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adve ...
problems that concerns playing a fair game over distance without the need for a
trusted third party In cryptography, a trusted third party (TTP) 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 c ...
. The term is also applied to the
theories A theory is a rational type of abstract thinking about a phenomenon, or the results of such thinking. The process of contemplative and rational thinking is often associated with such processes as observational study or research. Theories may be s ...
surrounding these problems and their possible solutions. The name comes from the
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 (such as poker). A small number of card ...
poker Poker is a family of comparing card games in which players wager over which hand is best according to that specific game's rules. It is played worldwide, however in some places the rules may vary. While the earliest known form of the game w ...
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 The mail or post is a system for physically transporting postcards, letter (message), letters, and parcel (package), parcels. A postal service can be private or public, though many governments place restrictions on private systems. Since the mid ...
, for instance), this suddenly becomes very difficult. And for electronic card games, such as
online poker Online poker is the game of poker played over the Internet. It has been partly responsible for a huge increase in the number of poker players worldwide. Christiansen Capital Advisors stated online poker revenues grew from $82.7 million in 2001 t ...
, 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 ( he, עדי שמיר; born July 6, 1952) is an Israeli cryptographer. He is a co-inventor of the Rivest–Shamir–Adleman (RSA) algorithm (along with Ron Rivest and Len Adleman), a co-inventor of the Feige–Fiat–Shamir identificat ...
,
Ron Rivest Ronald Linn Rivest (; born May 6, 1947) is a cryptographer and an Institute Professor at MIT. He is a member of MIT's Department of Electrical Engineering and Computer Science (EECS) and a member of MIT's Computer Science and Artificial Intell ...
and
Len Adleman Leonard Adleman (born December 31, 1945) is an American computer scientist. He is one of the creators of the RSA encryption algorithm, for which he received the 2002 Turing Award, often called the Nobel prize of Computer science. He is also kno ...
(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 In cryptography, a semantically secure cryptosystem is one where only negligible information about the plaintext can be feasibly extracted from the ciphertext. Specifically, any probabilistic, polynomial-time algorithm (PPTA) that is given the ciph ...
by
Shafi Goldwasser en, Shafrira Goldwasser , name = Shafi Goldwasser , image = Shafi Goldwasser.JPG , caption = Shafi Goldwasser in 2010 , birth_place = New York City, New York, U.S. , birth_date = , death_date ...
and
Silvio Micali Silvio Micali (born October 13, 1954) is an Italian computer scientist, professor at the Massachusetts Institute of Technology and the founder of Algorand. Micali's research centers on cryptography and information security. In 2012, he received ...
. The concept of multi-player mental poker was introduced in
Moti Yung Mordechai M. "Moti" Yung is a cryptographer and computer scientist known for his work on cryptovirology and kleptography. Career Yung earned his PhD from Columbia University in 1988 under the supervision of Zvi Galil. In the past, he worked at the ...
's 1984 book Cryptoprotocols.
Moti Yung Mordechai M. "Moti" Yung is a cryptographer and computer scientist known for his work on cryptovirology and kleptography. Career Yung earned his PhD from Columbia University in 1988 under the supervision of Zvi Galil. In the past, he worked at the ...
: Cryptoprotocols: Subscription to a Public Key, the Secret Blocking and the Multi-Player Mental Poker Game (Extended Abstract). CRYPTO 1984: 439-453.
The area has later evolved into what is known as
secure multi-party computation Secure multi-party computation (also known as secure computation, multi-party computation (MPC) or privacy-preserving computation) is a subfield of cryptography with the goal of creating methods for parties to jointly compute a function over their ...
protocols (for two parties, and multi parties as well).


Shuffling cards using commutative encryption

One possible
algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...
for
shuffling 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. __TOC__ Techniques Overha ...
cards without the use of a trusted third party is to use a
commutative In mathematics, a binary operation is commutative if changing the order of the operands does not change the result. It is a fundamental property of many binary operations, and many mathematical proofs depend on it. Most familiar as the name o ...
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 In cryptography, plaintext usually means unencrypted information pending input into cryptographic algorithms, usually encryption algorithms. This usually refers to data that is transmitted or stored unencrypted. Overview With the advent of comp ...
message. She encrypts this, producing a garbled
ciphertext In cryptography, ciphertext or cyphertext 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 ...
which she gives then to
Bob Bob, BOB, or B.O.B. may refer to: Places * Mount Bob, New York, United States *Bob Island, Palmer Archipelago, Antarctica People, fictional characters, and named animals *Bob (given name), a list of people and fictional characters *Bob (surname ...
. Bob encrypts the ciphertext again, using the same scheme as Alice but with another
key Key or The Key may refer to: Common meanings * Key (cryptography), a piece of information that controls the operation of a cryptography algorithm * Key (lock), device used to control access to places or facilities restricted by a lock * Key (map ...
. 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 such 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,
Dave Dave may refer to: Film, television, and theater * ''Dave'' (film), a 1993 film starring Kevin Kline and Sigourney Weaver * ''Dave'' (musical), a 2018 stage musical adaptation of the film * Dave (TV channel), a digital television channel in the ...
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 attack The known-plaintext attack (KPA) is an attack model for cryptanalysis where the attacker has access to both the plaintext (called a crib), and its encrypted version (ciphertext). These can be used to reveal further secret information such as secr ...
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
XOR Exclusive or or exclusive disjunction is a logical operation that is true if and only if its arguments differ (one is true, the other is false). It is symbolized by the prefix operator J and by the infix operators XOR ( or ), EOR, EXOR, , ...
ing 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" CH98 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 A security protocol (cryptographic protocol or encryption protocol) is an abstract or concrete protocol that performs a security-related function and applies cryptographic methods, often as sequences of cryptographic primitives. A protocol describe ...
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 In cryptography, a zero-knowledge proof or zero-knowledge protocol is a method by which one party (the prover) can prove to another party (the verifier) that a given statement is true while the prover avoids conveying any additional information a ...
s, so that players don't need to reveal their strategy to verify the game's correctness. The C++ library libtmcg TA05provides 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 OL05describes 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 In algebra, a homomorphism is a structure-preserving map between two algebraic structures of the same type (such as two groups, two rings, or two vector spaces). The word ''homomorphism'' comes from the Ancient Greek language: () meaning "same" ...
, 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 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 1985. ElGamal encryption is used in th ...
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 , computes ''E(ri)'', and publishes a non-malleable commitment to ''E(ri)'' # Players then publish their actual ''E(ri)'', and can verify that every player honors its commitment # Players compute \Pi E(r_i) = E(\Sigma r_i) , which produces a new encrypted card ''E(r*)'', with r* = \Sigma r_i # 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 AK99that does full shuffling using mix-networks. Note that the
random number generation Random number generation is a process by which, often by means of a random number generator (RNG), a sequence of numbers or symbols that cannot be reasonably predicted better than by random chance is generated. This means that the particular outc ...
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 ''k''th player truthfully generates a random r', the sum r = r* + r' is still uniformly random in . Measured in terms of the number of single-agent encryptions, the algorithm in OL05is 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
permutation In mathematics, a permutation of a set is, loosely speaking, an arrangement of its members into a sequence or linear order, or if the set is already ordered, a rearrangement of its elements. The word "permutation" also refers to the act or proc ...
of encrypted cards to the players. This can be done with any of several well-understood cryptographic protocols. # Players compute independent random numbers in , which are combined to generate a random number in , as in OL05# 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 is the game of poker played over the Internet. It has been partly responsible for a huge increase in the number of poker players worldwide. Christiansen Capital Advisors stated online poker revenues grew from $82.7 million in 2001 t ...
. 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

{{Reflist * 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. * TA05Stamer, H
Efficient Electronic Gambling: An Extended Implementation of the Toolbox for Mental Card Games
WEWoRC 2005, LN P-74, 1-12, 2005 * CH98Schindelhauer, C
A Toolbox for Mental Card Games
Tech. Rep. of Medizinische Universitat Lubeck. * OL05Golle, P
Dealing Cards in Poker Games
In Proceedings of the International Conference on Information Technology: Coding and Computing, (2005)


External links




LibTMCG - C++ library for creating secure and fair online card gamesDealing Cards with Cryptography
- A
Numberphile ''Numberphile'' is an educational YouTube channel featuring videos that explore topics from a variety of fields of mathematics. In the early days of the channel, each video focused on a specific number, but the channel has since expanded its s ...
video with
Ron Rivest Ronald Linn Rivest (; born May 6, 1947) is a cryptographer and an Institute Professor at MIT. He is a member of MIT's Department of Electrical Engineering and Computer Science (EECS) and a member of MIT's Computer Science and Artificial Intell ...
explaining the intuition behind the Mental Poker paper. Cryptographic algorithms