P2P card game: Shuffling without knowing the final order?

You can do this by making the secret starting state verifiable and guesses difficult:

• Have all players generate a new private/public key pair, send the public keys
• Let them shuffle their own decks
• Choose and/or exchange salts (see below)

• Generate signatures for the information you want to check:

  • Either a player's full deck if that can become known after the game or
  • the individual cards if you want to check after each card is revealed and not make the deck known if not all cards are played

  and send them over

• Have players choose a seed each to shuffle the opposing decks only. This ensures shuffling takes place with no knowledge (because the key pair was newly created and the cards have not been revealed, but have been "locked in place" by the signature(s))

After this you can use the same methods as a normal card game would use, for example addressing cards by their starting position in the deck or their current position. You need to keep track of the starting position in the hidden (signed) deck for each card, at least until it's revealed.

Depending on what you sign, verification takes place at different times:

• If you signed the deck, transmit the full deck after the game is over. A cheater will be revealed because of mismatched cards or the signature.
• If you signed the cards, check whenever one is revealed. The signature won't match if a player tries to cheat.

The strength of this algorithm depends on two assumptions:

1. Players can't choose a card that matches the transmitted signature.

   This should be inherent in correctly used modern cryptographic algorithms unless the key is chosen maliciously, with known collisions. You can protect against it by letting the opposing player(s) choose salts, which should prevent using known collisions.

2. Players can't verify the signatures without knowing the cards.

   This part is trickier, as the amount of plain texts is very limited if you sign individual cards only.

   Possible solutions:

   • Add a secret salt for each signature:

     This should not allow players to choose cards unless there is a collision weakness in the signing algorithm. Adding a salt to each card also prevents revealing cards that are the same.

     The salt is stored and revealed when the signature has to be checked.

   • Make guesses more expensive:

     (Checking the signature should already be somewhat expensive, this adds even more computations.)

     This can be done by using a (possibly known) salt and hashing the plain-text multiple times, but is possibly not as secure as the first option when used alone and is not as efficient. It can greatly increase the security together with a secret salt though, as the difficulty is multiplied.

     A side-effect is that it makes finding collisions much more difficult.

   If you want to future-proof the game while making it as fast as possible let the players choose minimums for the secret salt length and hash repetitions that are enforced for all players. You need to cap these when running a verification/leaderboard server though, to avoid a potential DoS.

   You can run verifications in the background to avoid delays, as a failure should terminate the game independently of its current state. (Make sure the transmissions can't be faulty though!)