Re: Pseudo random shuffle.

From: Vilhelm Sjöberg (vilhelm.sjoberg_at_gmail.com)
Date: 01/18/05 

Date: 18 Jan 2005 01:11:58 -0800

necoandjeff wrote:
> Bottom line, find any pseudo-random generating function, be sure
> that you and your buddy feed it the same seed number to start with,
> and you will both be assured of the same random sequence of cards.

This is not quite enough, because while you will end up agreeing on the
shuffle, this also means that both players are aware of the state of
the shuffled deck. Which is less than ideal if you're going to play
poker, for instance. :)

Nevertheless there are crypto protocols that let you keep things
appropriately concealed until the end of the game. A simple variant
uses as its basic building block a commutative cypher, that is a cypher
such that a message that was encrypted first with key K1 and then with
key K2 can be decrypted either by first decrypting it with key K2 and
then decrypting the result with K1, or in the other order. For instance
RSA has this property.

Using this we can create the shuffle as follows. Alice creates 52 cards
and encrypts them all seperately using Ka. She sends them in random
order to Bob, who encrypts them all using Kb and publishes the result
in random order. Now we have a permutation of cards each of which is
encoded with both keys, but were neither player knows what order they
are in. In order for say Bob to privately look at a card, he would ask
Alice to decrypt it using Ka, and then he can himself undo key Kb and
look at it in plaintext. At the end of the game, both keys are made
public and each player can look back at the record of the game and
verify that nothing untoward happened.

It strikes me that this still doesn't quite do everything you want,
because in poker it is usual for folding players to discard their cards
face-down, never letting anyone know if they were bluffing or not. I'm
not sure if it would be possible to do something to solve that problem,
short of using a trusted third party.

Anyway, the algorithms are there. The user interface, of course, is a
Simple Matter of Programming. :) (But really, one would imagine that
someone had written software to do this already. The protocol has been
in introductionary crypto textbooks for, like, forever.)
Sorry for the off-topicness, btw.

//Vilhelm

Relevant Pages

  • Poker Strategies Teil 2 Author Selzer-McKenzie
    ... bad play (there would have to be about $50 in the pot already to make ... one making a bad play. ... The general principle about free cards is this. ... 9Most modern cardrooms have rules protecting players against ...
    (de.etc.finanz.misc)
  • Re: what kind of card games does max all play?
    ... This article is about the popular poker variant. ... Texas hold 'em involves community cards available to all players ... Similar games ...
    (rec.sport.pro-wrestling)
  • |[4E] Marky Mark
    ... I scour the dealer's hall looking for interesting little knickknacks that promise to help me run my game faster or help me convey information to my players with ease. ... You're in the middle of a tense battle. ... Cards and More Cards ...
    (rec.games.frp.dnd)
  • Re: Epilogue: An open letter to FIFA...
    ... Thierry Henry in the first minute of the match? ... the professional fouls which cause actual harm to other players. ... effort that Sepp or FIFA can make to promote the game. ... cards in all respects of Fair Play violations ...
    (rec.sport.soccer)
  • [Review] The Great Space Race
    ... because every once in a while, I want to play a game that I can just ... Players take one of eight control consoles that match one of the eight ... events must play each of them - in initiative order, and draw cards to ... from their ship. ...
    (rec.games.board)