Random permutation of cards where each player knows only his cards

75 Views Asked by At

On a trip, four friends want to play a card game, where $n$ cards must be dealt among the players before the game starts. However, they forgot the cards, so they HAVE TO play with imaginary cards (there is no paper etc. at hand).

The game cannot be played with less than four players, so the friends cannot choose one of them as a dealer, who would randomly shuffle a deck of cards in his mind, and secretly tell each of the others, which cards he gets.

How to solve their problem, i.e., how to (randomly) permute a deck of cards, so that each of the players knows only his $n/4$ cards?

2

There are 2 best solutions below

1
On BEST ANSWER

One can use a slight modification of the random coin flip algorithm. As in the latter, it is essential that the cryptographic protocols used by the players are commutative, i.e. it does not matter in which order decryption/encryption with different keys is performed. (E.g. they can XOR the plaintext deck with their own private keys.) Now you do as follows. $A$ shuffles the deck, encrypts each card with his key, and passes the deck to $B$. $B$ shuffles further, encrypts with his own key, and passes the deck to $C$, etc. Once the deck is shuffled and coded by all four players, $A$ decrypts anything but his own cards, i.e. the first $n/4$ cards, then $B$ decrypts anything but the cards $n/4 +1 $ to $n/2$, etc. Finally, they end up with the deck where the cards $1$ to $n/4$ encrypted by $A$'s key; $n/4+1$ to $n/2$, by $B$'s key etc. This can be passed to all players, so everyone can identify his cards (but not the cards of other players).

0
On

Theoretically possible solution for the values of $n$ big enough, is the following:

  1. Players injectively map the cards to the set of prime numbers, i.e., every card $j$ gets its own prime number $p_j$.
  2. Each player $i$ chooses his $n/4$ cards and computes the product $\Pi_i$ of the corresponding primes and report it to the other players.
  3. If the product $\Pi_1\Pi_2\Pi_3\Pi_4$ equals the product $\Pi_{j = 1}^n p_j$, the cards were successfully dealt. Otherwise, we go back to step $2$.

Two problems:

  • For a human, it is hard to calculate $\Pi_i$.
  • We may have to repeat step 2. many times.