Mental poker

From Wikipedia, the free 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 problems apply. 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 cames, 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-encyption protocol).^[1]

Contents 1 Shuffling cards using commutative encryption 1.1 The algorithm 1.2 Weakness 2 References

[edit] 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 this 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.

[edit] 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 that each 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 keys B₆ to B₁₀ which are required to decrypt the cards.

[edit] Weakness

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.

[edit] References

• ↑  A. Shamir, R. Rivest, and L. Adleman, "Mental Poker", Technical Report LCS/TR-125, Massachusetts Institute of Technology, April 1979.
• 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.