Online Poker

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.

Of bicycles and go-karts

In the realm of small transportation, there are (among many other choices) bicycles and go-karts. They are different beasts, built different ways for different purposes. Some may consider bicycles more elegant and precision machines, and go-karts can sometimes be a bit sloppy, held together with duct tape and baling wire, but they can go pretty fast. (Yes, bicycles can go quite fast also but there are different approaches to making them fast and they can be quite variable)

So, if you take someone who is a decent bike builder and show them a go-kart, explain the basic principles of operation, give them the parts to build a go-kart, and suggest that they use the parts to build a go-kart and expect that their general mechanical knowledge from building bikes will be sufficient to let them actually handle the building process, then you would expect them to build a go-kart, right?

NO.

They will use the parts you gave them to try and build a bicycle. However, go-kart parts are not bicycle parts, so they will try to make do.

A bicycle has 2 wheels, but their parts box has 4 (that are qiute different). So they'll put one in front and one in back, and then since there's 2 extra, they'l put those in the back too.

A bike doesn't have an engine, so they won't quite know what to do with it. But it has to be there, so they'll strap it to the front. Not connected to anything, just strapped there. For propulsion, a bike uses pedals and a chain; there's a chain drive from the engine that looks like a bike chain (only a lot shorter), so that will work. And the brake and gas pedals look can double as bike pedals in a pinch, so those get strapped onto the chain somehow.

A go-kart frame is rather square-ish compared to a bike frame, but that'll have to do. Stuff can get bolted onto it somehow. The seat goes sort of sideways in the middle, right?

The steering wheel is a common enough thing that they realize it's for turning the wheels, even if it's different than bike handlebars. It gets bolted in there too and wired up to the single front wheel.

So after all this you have a go-kart frame all bent out of shape in such a way as to sort of resemble a bicycle, that you have to pedal very ineffectively, with no brakes, that you can barely control, and carrying the extra weight of a useless engine, that you can't make go very fast. But it DOES go.

And the builder?

They complain that the parts you gave them don't make a very good bicycle.