# Shared secret: Generating Random Permutation

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

-
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
To ameliorate the sore loser phenomenon, the game could be played with virtual "poker chips" that cost players something but have no value until cashed in. A player who abandons the game would also be abandoning all his or her chips. I imagine that such virtual poker chips could be designed that do not require a central authority. –  Brock Hansen Feb 17 at 20:30

Can you use threshold encryption and a mixnet? It might not be the fastest thing in the world but it uses well-understood components.

# Setup

1. Every player generates an ElGamal keypair and proves knowledge of their secret key. The joint public key is the product of all public keys. (If you're worried about reset attacks, look up "Pedersen threshold key generation" for a more involved version).

2. Anyone creates encryptions of the numbers 0 through 31 under the joint public key, together with non-interactive proofs of knowledge that these are really encryptions of 0 .. 31. Everyone else verifies the proofs.

3. The players take it in turn to shuffle the cards by applying a mixnet to the list of encryptions. (Wikstrom's "Verificatum" is the fastest mixnet I know of.) Everyone verifies everyone else's mixnet proofs. The result is a list $L$ of 32 shuffled, rerandomised, encrypted cards.

# Drawing cards

1. The first player throws a 32-sided dice as you discribed earlier. (Instead of encryptions, I'd use homomorphic commitments, but the result is the same.) This gives a random integer $i \in [0, 31]$ which all players see. The first player takes card $L[i]$, leaving 31 cards in the list.

2. All players threshold-decrypt the chosen card towards the first player. That is, they create a threshold-ElGamal decryption share for the specific ciphertext $L[i]$ and send it to player 1. These shares should be accompanied by Chaum-Pedersen proofs (w.r.t. the individual public keys) that the decryption shares are correct.

3. The next player throws a 31-sided dice (again in public) and "removes" the card at the correct index. All players produce a decryption share for the relavant card and send it to the player who gets the card. Repeat whenever a new card needs to be dealt.

# Revealing cards

When a player "draws" a card this way, they can decrypt it and learn its value (in 0-31). To reveal the card to the other players, the card-owner simply publishes all decryption shares for this card, including their own. Everyone else can check the NIZK proofs to convince themselves that the card is correct.

-