Cryptography for P2P card game

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'v开发者_StackOverflow中文版e 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.

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.

I want to describe one idea which came into my mind rather quickly. I don't know if it serves all your needs, so please feel free to comment on this.

Assume player A has cards A1, A2, A3, ... from a set represented by numbers 0, 1, ... N-1. These cards might be also separated into piles but this does not change the following.

Instead of handling these cards with a single list [A1, A2, A3, ...] you can instead use two of them [A1_a, A2_a, A3_a, ...] and [A1_b, A2_b, A3_b, ...] where one is with player A and the other with player B. They are generated in such a way, that each one is random (in range 0...N-1) but both are correlated such that A1_a + A1_b = A1, A2_a + A2_b = A2, ... (all operations modulo N).

• Thus no player actually knows the cards without access to the complementary pile (i.e. he cannot reasonably change his cards)
• Whenever you need to know a card both players show their corrresponding value and you add those modulo N
• you can implement things like "draw a card" quite easily, both piles just have to be treated the same way

The traditional Mental Poker scheme is overkill. Your situation is actually much easier since there is no shared deck. You could do something like this:

Player A takes his cards and encrypts them with key Ka. He sends them to B who shuffles them, encrypts them with key Kb. Each time A wants to play a card, he asks B for the (Kb) decryption of the next one. A decrypts this to find what card he drew. At the end, A and B reveal Ka and Kb and compares them with the game log, which should prevent cheating.

Updated: On reflection, here's a simpler solution: As above, player A encrypts his cards and sends them to B. B shuffles them. Whenever A wants a card, he tells B which deck he's drawing from. B returns the (encrypted) card from the appropriate pile.

While a central server would probably be the easiest way, if you want to avoid it you could use a distributed system, wherein everybody playing the game is a storage host for other players' decks (not for himself or his opponent, but anybody else). I believe Limewire and Bittorrent both work this way, so you might gain some ideas by studying those sources.

Maybe the players could exchange hashes of their piles at the start of the game.

Then when the game is complete, the players exchange the actual composition that their piles had at the beginning of the game. Now the player's client can check that it matches the hash they got before and then check that all the moves that were made would work with those decks.

The only problem is how the decks are shuffled initially. You would need to make sure the player cannot just start his deck in any order he chooses.

Maybe have the players generate their initial deck order by getting randomness from some specific source.. but in a way that the other player cannot work out what the other player's deck orders are until the end of the game, but can still check that the player didn't fiddle their decks. Not sure how you could accomplish that.

Edit:

Another idea. Maybe instead of generating the random decks at the beginning of the game, they could be generated as the game goes on.

Each time a player needs to take a new card from the pile, their opponent sends them some random seed that is used to choose what the next card will be.

That way the user has no way of knowing in what order the cards will follow in their decks.

I'm not sure how you would stop the other player from being able to tell what card they would be picking for their opponent. If the seed was used to select a card from some kind of randomly ordered list of the cards that the opponent had a hash of to verify.. they could check all the possible combinations of cards and find out which one matched the hash, thereby being able to dictate which card they wanted the other player to draw by sending them a seed that would cause that card to be selected.

this is an adaption of Acorns approach:

setup:

each player has their deck (totally ordered set(s) of cards) ... those decks are public and are in natural order

each player needs a asymetric (signing) keypair, public keys exchanged

now to the randomness problem:

since a player may not be able to see in advance what cards they will draw, the opponent will be the source of our randomness:

when we need some random value, we ask our opponent ... random values are stored along with the moves to be checked later

since our opponent may not be able to manipulate the order of our cards, we take that received random value and sign it with our private key ... the value of that signature will be our RNG seed (unpredictable for the opponent), and later the opponent may verify the signature against the random number he/she generated (so we store the signatures too, and exchange them after the game)

since we can do this random number exchange every round, the random values are not known to the player in advance -> no peeking at the order of our stack

and since we now have a seeded RNG we can get random values derived from that "shared" random value ... that way we can draw "random" (completely deterministic, with repeateable verifiable results) cards from our deck ... the deck/pile won't need to be shuffled, since we can get random positions from our RNG

since we have all exchanged random values, the signatures, the initial decks (in total order), and all moves, we can replay the whole game afterwards and check for irregularities