-- 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?
