Imagine that 4 computer scientists encounter each other in the wilderness, each carrying nothing but a laptop computer and some networking supplies. They get to chatting, and they realize that they have a shared interest in the game of Hearts. But they have no playing cards. So they want to network their computers together and play Hearts.
BUT, they also know that all each of the 4 is insanely competitive, perfectly ruthless, and a maximally brilliant computer programmer. So they want to know if it’s possible to write a fair Hearts program in those conditions. Obviously, they can network their computers together and, once the cards are dealt out, play out a game of Hearts. But how do they randomly deal the cards? They assume that every bit of information that ever travels through one of their laptops will be viewed and exploited by the owner of that laptop. So if the way their shuffling works is that one computer shuffles a virtual deck and then sends to each of the other 3 computers the contents of that player’s hand, then whoever owns the computer doing the shuffling could (and would) be cheating.
Is there a way for them to cooperatively shuffle the deck, such that each of the 4 ends up with no information other than the 13 cards in his or her starting hand?
Assume that they each have access to a perfect random number generator, even if it’s just randomly hitting keys and measuring the number of milliseconds between keystrokes, or something like that.
(If we assume infinite computing power, then this problem can be solved if we can solve the superficially similar problem of verifying that a deal is correct, that is, that all 52 cards are present once and only once. If we can verify deals, then we can just randomly have each player select a 13 card hand, verify, and repeat until acceptable hands are found.)
Here is a solution for the “related” problem. I am assuming there is no collusion between multiple players but that each player is cutthroat in trying to win.
Each pair of players agrees on a shared secret encryption key. They encrypt each card in their hand with this shared key and send the results to a third player. The third player examines the hands and identifies if any cards are duplicated.
This requires a reasonably strong encryption system to work. In particular, given twelve of the cards in plaintext, the thirteenth card should not be able to be determined by the third player – as the hand goes on the contents of each player’s hand becomes public and thus “known plaintext” attacks become viable. However, while I’m not an expert on encryption, I am reasonably sure that such systems exist.
However, even with infinite computing power, this isn’t a solution. A cutthroat player could modify their hand generation algorithm to create a “good” hand (for example, always choosing a hand containing all the clubs on a hand when cards aren’t being passed). There is no way for the other players to prove whether or not this player’s hand was actually generated randomly, and eventually (if everyone else was playing ‘fair’), the corrupt hand would end up being the 13 remaining cards that didn’t get generated by the other three players.
A real example doesn’t have to be this ridiculous–even modifying the random algorithm to give you a slightly better hand 50% of the time would make a significant difference over the course of a game.
I used to play the version of Hearts that comes with Windows with my co-workers via our network. It appeared built-in back then to search for others wishing to play Hearts that were connected to the network at a given time.
One woman who played me wondered how I got so good. She didn’t realize that I sat directly behind her in a common office and had full view of her screen. :rolleyes:
In Theoretical Computer Science, this problem was solved long ago under the name “Mental Poker” (instead of Hearts). And of course there’s an article about it at Wikipedia. I have a copy of the Goldwasser and Micali paper it cites. But the article seems to stop short, not covering what was done shortly thereafter.
This is solvable by having each person use a random key that was publically generated and communicated by someone else to generate his random hands, also using a public key for which he’s published the private key but not the public key, so that only he can encrypt things but anyone can decrypt them. This allows verification after the fact that the hands were in fact randomly generated.
Although the mental poker algorithm is a much better solution.
There are already cryptographic protocols to play fair poker. Surely one can be adapted.
Basically, Alice, Bob, Carol, and Ted agree on an encoding of each card and on a commutative cryptosystem. Alice encrypts all the cards with her key, then Bob with his, then Carol with hers, then Ted with his. Then they divvy up the encrypted cards and pass them around, each person taking of his or her encryption until the last person to decrypt each set of cards is their holder.
But you know which cards you encrypted and what they are. So how do you not know that the encrypted ace of spades went to player B. It still leaves a Divying up problem.
I think the way is similar to what you said, but with several more layers - I am sure this is the least elegant solution possible but here goes.
essentially a shuffle by divying. Say One computer “randomly allocates 13 cards each”. You take each card and PK encrypt it, say X(cards). Then you pass those 13 cards “at random” to your three coplayers. They then add another layer of encryption say B encodes to make Y(X(cards)) and passes it again. This is repeated say 100 times. At the end the public key decryptions are revealed and the final player then decrypts his card back through the lengthy PK decryption sequence. Even though each player knows the path of each card HE HAS went (say A to B to C to A to D etc to decode it), the number of random moves means that it is impossible for another player to be sure where any of his initial cards went.
probably something wrong here but not bad for 2 minutes thought
you would also need to PK encode the sequence as you passed the card too, otherwise A would know that on the last pass he passed some of his original cards to C, even if he didnt know which ones.
Actually there is a flaw thinking about it more. How to stop the second to last player decrypting the cards he just passed?
This also works for hearts because all the cards are used. It wont work for Poker as only a few cards are used, so you would know some of which cards are in the deal - hmmmmm.
Even if you shuffled the entire deck like I said and just asked them to select 5 cards for their hand, you couldn’t stop them decrypting the others. I think then the answer is that at the end of the “shuffle” the player announces which 5 of the 13 he is using in his hand and only then is then given the sequence of passes by the second to last player for those 5 cards.
Still have to stop the second to last player decoding everything. Give me 5 minutes - sorry for thinking on the fly
It can be done but it complicates the passing and would need to be done each pass. I will go through it if anyone is interested but I think Ive bored people enuff today
I was thinking if you could do this without any encryption security. Perhaps if you write a paralel process program that requires all four computers to run, maybe combined with an extensive randomisation of which computer runs which module and holds which data.
Actually, I think probably the simplest solution to implement would only need 1 computer. They code one version of hearts together and lock that laptop into user mode with no admin rights. After a move is made, the program locks the screen, and the laptop is passed to the next player. When unlocking the screen, the next player’s hand is shown, etc. Any kind of messing is detected immediately as the one laptop is inspected by all four players each round. No real security is necessary.
This way they can four times longer on their collective batteries also.
Another possible way is that the four users each have to write a program to code their gaming strategy. They are allowed to change their code after each round, but when they are done playing, they will have to show every version of their code to the other players. They can then verify whether there was any cheating in the code or any messing with the code afterwards easily enough by running the same deck with the versions of the code for any of the rounds and see if the same game results would result (assuming that the code doesn’t have random elements of course, but even then you could require the random values to be stored in a log file also).
actually the Winkepedia article http://en.wikipedia.org/wiki/Mental_poker is much much more elegant method than mine which I should have read before these lengthy posts. :smack: Mods please feel free to remove my ramblings and I will go back to hibernation.
Each person creates his own set of modules that perform a certain set of tasks and must respond to a particular API.
Commands sent to a server module are non-encoded plain-text items, so everyone can see what commands were sent, by who and to whom (particularly the receiver, as he is perfectly open to see everything happening in the internals of his personal modules.) The return values of the commands, however, are returned using public key encryption.
Modules that are listed as Dealer mean that only the dealer’s module is valid.
Each player has a unique id.
Module 1 - Deck Server
Module 2 - Shuffle Server
Module 3 - Hands Server
Module 4 - Game Client
Deck Server - Dealer
char get_card(int uid);
Will get a card off the deck if there is one available for the player, otherwise it will return -1. Return value cannot be used until unmapped
Shuffle Server - All
void shuffle();
Tells the module to reset its internal mapping to a new random set.
char unmap(char mapped);
Translates a mapped card value into an actual card. All servers must be called (in order of their uid, increasing) to get a final unmapping.
Hands Server - All
char[52] get_list();
Returns a list of all the cards held by this player that can be seen by others. Values are unmapped.
I’m not sure of the rules of hearts, but with this setup you should be able to play any game. The dealers deck is simply a (potentially) random list of 52 values, and meaningless until unmapped using the other player’s unmapping functions. If someone tried to run more numbers than he is allowed through everyones functions, to see what all the translations are, everyone would see it and he would be kicked–and it does him no good to unmap cards that aren’t his own as then his hand wouldn’t match up with everyone elses and in fact, he wouldn’t know what his own hand is.
No, you miss the point. Alice encrypts the entire deck.
Okay, try this. Say you’ve got a real deck. Put each card in a box. Alice puts locks to which only she has the key on each box. Similarly, so do Bob and Carol and Ted. Then they divide them up randomly and take off their locks, so the last person to take off the locks of a given set of cards (and thus the only person who can see what they are) is the person whose hand they are.
Bob then offers the decryption key to the other 3 players, and all four use their own, newly generated unique keys to encrypt their hands. As each hand is played, only the cards actually played get decrypted.
Too much power in Bob’s hands, especially since many encryption systems leave ways of marking the cards. You want something so that nobody holds all of one step in their hands.
Joe takes 26 cards, and Mary takes 13 from him. So, Joe knows which cards Mary took. They key for all the cards is the same. When Bob reveals the key, Joe knows exactly which cards Mary has.
The idea was that Joe wouldn’t know what 26 cards he had until after Mary already took her 13, assuming that the act of “taking” completely removes all info on the cards taken.
But Mathochist already pointed out the flaw in my simplistic (KISS principle) idea.
Actually, from what I’ve seen of cryptologic protocols, I’d advocate a different reading of the same acronym: Keep It Symmetric, Stupid.
I don’t mean that the encryptions should be symmetric (a.k.a. private-key), although ultimately those sorts of algorithms tend to be stronger for the time spent. What I mean is that to whatever extent two people are doing the same high-level thing (playing poker, verifying each other’s identity), they should perform the same low-level steps. In Diffie-Hellman, both Alice and Bob do the exact same thing. In my rough outline of a hearts game, Bob and Carol and Ted and Alice all do the same thing at every step.
They code one version of hearts together and lock that laptop into user mode with no admin rights. After a move is made, the program locks the screen, and the laptop is passed to the next player. When unlocking the screen, the next player’s hand is shown, etc. Any kind of messing is detected immediately as the one laptop is inspected by all four players each round. No real security is necessary.