Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

-- or: How to Play Poker Without a Dealer

I know this question is long but it's a really interesting theoretical problem about shared secrets and multi-party computation.

General Problem: "Shared Random Generation"

Consider the following scenario: $N$ parties want to play a simple game. For this, some randomness needs to be generated (e.g. throwing some dice, shuffling cards etc.; these two concrete kinds of secret information will be used throughout the rest of this text). The game should be played decentrally, i.e. no "dealer" should be required on some central server; neither should one of the N parties be the "host" which knows more than the others (the "secret").

The secret needs to be generated at some point during the game and then be fixed such that no player should be able to know, or still control the secret (after it's generated). There should be the possibility to unveil the secret to a single player during the game (think of drawing a card from the deck or looking at the dice while they're hidden to the other players), or of course to all players.

Assume that there are $N$-to-$N$ private channels for communication given (encrypted, verified, etc.), so each player can communicate to each other player securely. A broadcast mechanism might be implemented separately or on top of the peer to peer channels.

Solution for Throwing Dice

One concrete scenario could be a simple dice game like Mia (or Liar's Dice). One player throws two dice in a dice box. He's allowed to look at the dice without the other players seeing them. At some time, another player can uncover the dice to the whole table. The actual game rules aren't important. What's important is that noone except the player who looked under the dice box knows their value.

A solution might look like this: To throw a die (unimportant who would it in the real world), each player generates a random integer, at least in the range $[0,6)$. The value of the die is implicitly defined by the sum of those integers modulo $6$, but noone knows this result. Each player now generates a random key and encrypts the random integer using a good symmetric encryption like AES. The plaintext is appended or prepended with some large enough constant, such that it's infeasible to find another key which will decrypt the message to a later chosen plaintext (important to avoid "late manipulation"). The encrypted texts are shared among all players. As soon as a player $p$ is allowed to know the value of the die (when he's allowed to look under the dice box), all other players privately reveal the key they used to encrypt their random number. Player $p$ can now decrypt the messages, verify them (by looking at the prefix / appendix) and finally compute the value of the die. Noone except him can do the same. To unveil the die to the whole table, all players broadcast their key.

To throw multiple dice, we can simply repeat the steps (independently) above for all dice to throw.

Shuffling a Deck of Cards

The real question is now about extending this idea to shuffle a deck of $M$ cards, e.g. $M = 32$ for Skat. Shuffling $M$ cards is finding a random $M$-permutation. As soon as the cards are shuffled, their order is fixed. Then, each player is allowed to draw cards from the deck; for simplicity imagine a game in which each player draws a single card in a certain order. Of course, each player hides his card to the others.

When the first player draws one card, that's like throwing an $M$-sided die. However, as soon as the second player should draw a card, there are only $M-1$ cards left, and nobody except the first player knows which card is missing (so the cards are somewhat dependent), so even throwing an $M-1$-sided die will not solve the problem. This renders the method from above insufficient (if not useless) here.

Another approach would be that all $N$ players generate a random $M$-permutation. The order of the cards on the deck is then defined by the composition of these permutations. (Imagine in the real world that the first player shuffles the cards, then the second player shuffles these cards again; each player knows his own permutation but not the composition.) The protocol could then work like this: The player who draws a card sees the index on the deck (first card to be drawn: 1, second card: 2, etc.); he needs to apply the inverse final permutation; this can be done by applying the inverse of each individual permutation one after the other. But he needs to ask the players for their secret piece at one particular position (note that he should finally be able to see only a single card, that is evaluate the inverse permutation at one index only). The last player to be asked (the one who shuffled the deck first) then knows which card was drawn, breaking one requirement.

The subtle difference between these two problems is that when drawing cards, the result of the "random events" are dependent on each other. Once the first card is determined, there are only $M-1$ cards left; choosing one from them randomly requires the knowledge of this card. To circumvent this fact we need to generate a proper permutation in one go, which seems to be not possible while satisfying the requirements for fair game playing.

Another idea currently not leading to anything usable might be to generate $M$ random numbers in the range $[0,M)$, using $M$ different $M$-sided dice, and then detect and solve multiple occurrences of the same value (something like a "shared hashing" algorithm could help, if such a thing exists, that is computing the hash of a sum (modulo $M$) using multi-party computation).

Does anybody have an idea to solve this issue? Any hints pointing me in the right direction?

share|improve this question
One can usually avoid non-standard cryptographic assumptions like the existence of a "large enough constant, such that it's infeasible to find another key which will decrypt the message to a later chosen plaintext". $\:$ (In fact, that assumption would not necessarily suffice, since it might still be feasible to open to a different value that cannot be chosen.) $\;\;\;$ The basic good idea is to have everyone commit to an element of $\:\{0,1,2,3,4,5\}\;$. $\;\;\;\;\;\;$ –  Ricky Demer Jan 6 at 19:01
You may find the following paper interesting: people.csail.mit.edu/rivest/ShamirRivestAdleman-MentalPoker.pdf –  J.D. Jan 6 at 19:12
Thanks @J.D. This paper seems to be about the EXACT same problem. What a coincidence! –  leemes Jan 6 at 19:55
Please note that any mental poker protocol would leave you with a problem of how to fold, if there are more than two players. If all players have to be present to decrypt the next card, one player might simply go offline and make it impossible for the remaining players to complete the game. If you solve that by using threshold secret sharing, you introduce a possibility of collusion. –  Henrick Hellström Jan 6 at 20:25
@HenrickHellström Yeah I realize that extending Mental Poker from 2 to $N$ players is a remaining problem, but when I require all $N$ player's machines to remain present (even when it's not their turn) I guess it's straightforward. The paper uses double encryption, that becomes arbitrarily long chained encryption. I hope this works; I haven't thought enough to be sure. –  leemes Jan 6 at 20:31
show 6 more comments

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.