Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

More formally:

I want to find an algorithm, if possible, that allows player to take turns in drawing cards from a deck such that:

  1. The cards drawn are random, and players can't influence the order
  2. 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:

  1. Each player choose a random permutation of [1..N]
  2. He writes it down, hashes it, signs the hash, and passes the hash+signature to the other player
  3. 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
  4. 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.

share|improve this question
    
how... is this a mathematical problem? –  Jan Dvorak Dec 26 '13 at 20:30
    
how would you categorize it? –  miniBill Dec 26 '13 at 20:32
    
if you want help on securing your source of randomness(from inspection, predictions and modifications), probably Information Security; if you want help looking up the right library calls, try seaching on Stack Overflow. If you want help on a shuffling algorithm, Stack Overflow should point you to the Fisher-Yates algorithm. –  Jan Dvorak Dec 26 '13 at 20:39
1  
or, is that you lack a central server to act as an authority, and yet you want every attempt at tweaking the rolls to be detected or subverted by the other party? –  Jan Dvorak Dec 26 '13 at 20:42
    
If you want to protect the server rolls from man-in-the-middle attacks, Information Security seems like an appropriate place to look for an answer –  Jan Dvorak Dec 26 '13 at 20:45

1 Answer 1

up vote 3 down vote accepted
+50

This Wikipedia article on "mental poker" describes such an algorithm. It's a bit complicated, but that's only to be expected.

share|improve this answer
    
@miniBill: Thank you for accepting my answer! If your intention was to award me the bounty too, then you have to do this separately. (I have made this mistake myself in the past.) –  TonyK Dec 27 '13 at 17:17
    
I had to wait for some hours before being able to award it :) –  miniBill Jan 1 at 20:19

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.