I want to know whether there is an algorithm for randomly and securely drawing cards from a deck.
I was thinking about a way to play deck-based games online with no trusted party and no way to cheat.
I want to find an algorithm, if possible, that allows player to take turns in drawing cards from a deck such that:
- The cards drawn are random, and players can't influence the order
- No player can have more information about his opponents cards and the cards left in the deck then it would have in a real world game (e.g.: when the deck is empty every player knows the other player cards anyway)
EDIT: I'll clarify some points (thanks to the comments):
I'm not interested in code, nor implementation details, but what I'm looking for is an algorithm, in its abstract description.
I'll write an example of what I'm looking for in the case of two decks of $N$ cards:
- Each player choose a random permutation of [1..N]
- He writes it down, hashes it, signs the hash, and passes the hash+signature to the other player
- When a player must draw a card the other player chooses a number $i$ at random ranging from 1 to the number of cards in the deck, the player then chooses the $i$-th number in his random permutation
- At the end of the match the players exchange the original permutations, and check if the game was valid
Neither of the players can control the drawing order, and neither of them can cheat without being caught (signing the hash means that in case of dispute the player must provide the original shuffle) (for the actual game players would need to sign moves too, but that's beyond the point).
The problem is doing this with a single deck.