Cryptography for P2P card game

Question

I'm considering writing a computer adaptation of a semi-popular card game. I'd like to make it function without a central server, and I'm trying to come up with a scheme that will make cheating impossible without having to trust the client.

The basic problem as I see it is that each player has a several piles of cards (draw deck, current hand and discard deck). It must be impossible for either player to alter the composition of these piles except when allowed by the game rules (ie drawing or discarding cards), nor should players be able to know what is in their or their oppponent's piles.

I feel like there should be some way to use something like public-key cryptography to accomplish this, but I keep finding holes in my schemes. Can anyone suggest a protocol or point me to some resources on this topic?

[Edit] Ok, so I've been thinking about this a bit more, and here's an idea I've come up with. If you can poke any holes in it please let me know.

At shuffle time, a player has a stack of cards whose value is known to them. They take these values, concatenate a random salt to each, then hash them. They record the salts, and pass the hashes to their opponent.

The opponent concatenates a salt of their own, hashes again, then shuffles the hashes and passes the deck back to the original player.

I believe at this point, the deck has been randomized and neither player can have any knowledge of the values. However, when a card is drawn, the opponent can reveal their salt, allowing the first player to determine what the original value is, and when the card is played the player reveals their own salt, allowing the opponent to verify the card value.

Answer 1

Your problem is the famous Mental Poker Problem in cryptography (this was one of my favorite parts of crypto-class in college). It is possible, and it has been solved (in part, like all things crypto, by Ron Rivest), as long as you don't mind a huge performance hit.

Check the wiki page for more details.