I've been thinking about a scheme for online poker where cheating is impossible.
By cheating, I mean strictly two things:
- no proper subset of the players can control the cards dealt
- no proper subset of the players can know any cards dealt to any players outside of the subset
In other words, the dealer can't stack the deck, even with help; and you can't peek at other players' cards, even if you control the server. An immediate consequence of this is that there is no single trusted entity, house or otherwise.
Here is the basic scheme I propose:
Each player generates a secret encryption key (K).
The dealer shuffles the deck and encrypts each card with his key.
[the dealer now has complete knowledge of the deck, but no one else does]
Each player in turn repeats this process (shuffle, encrypt).
[now no player can tell what any card is by looking at it, and the order has been randomized so it is different from the dealer's original shuffle]
The encrypted deck is visible to all.
To deal a card, the card is given to each player, who partially decrypts that card with their own key and passes it to the next player who does likewise, ending up with the recipient of the card who decrypts it ending up with the real card. In this way, each player other than the recipient sees only a card that has been encrypted by one or more keys.
When the hand is over, all players can reveal their secret encryption keys so the encryption steps can all be verified.
This scheme requires an encryption method that can be applied multiple times with different keys, and that can be decrypted with those same keys in any order, such that decrypting with fewer than all the keys provides no information about the fully decrypted message.
The simplest example of such an encryption method I can think of is a caesar cipher. Each player picks a number between 1 and 52, and rotates each card by that amount. To decrypt, they each rotate it backward. But this has a few flaws. The relative positions of the cards stay the same (a king is always one more than a queen, etc.) And revealing any single card reveals all cards belonging to that player. So something stronger is needed.
Clearly, each card must be encrypted by itself. A caesar cipher plus a keyword (a Vigenere cipher) won't work, since it is position sensitive, and the cards get reordered.
A simple one-time pad approach should work, where the pad is a permutation of the numbers from 1-52, and each number is replaced with the number in that order. The pad is completely private, so there is no problem with exchanging them. Implementation would be straightforward.
The devil with encryption is that there are potentially so many non-obvious flaws. Are there any places where my proposed scheme fails?
An abstract example:
There are 3 players, A, B, and C. A is the dealer. He shuffles the deck, encrypts each card with A, passes it to B. B shuffles the deck, encrypts each card with C. C shuffles and encrypts and returns the deck to the dealer. Now the deck is in a random order, and each card is encrypted with ABC(c).
A deals a card to B: he first decrypts the card with his own key, leaving BC(c). He gives the card to C, who decrypts it with C leaving B(c). The card is then passed to B who can decrypt it leaving plain c.
A deals a card to C: he decrypts it with A, leaving BC(c). He gives it to B who decrypts it leaving C(c). The card is passed to C who can decrypt it to plain c.
A deals a card to himself: he passes the card ABC(c) to B, who decrypts it leaving AC(c). It is passed to C which decrypts it leaving A(c). It is returned to A, who can decrypt it to plain c.
