|Previous||Table of Contents||Next|
Ideally, step (10) would not be necessary. All players shouldnt be required to reveal their hands at the end of the protocol; only those who havent folded. Since step (10) is part of the protocol designed only to catch cheaters, perhaps there are improvements.
In poker, one is only interested in whether the winner cheated. Everyone else can cheat as much as they want, as long as they still lose. (Actually, this is not really true. Someone can, while losing, collect data on another players poker style.) So, lets look at cases in which different players win.
If Alice wins, she reveals her hand and her keys. Bob can use Alices private key to confirm that Alice performed step (2) correctlythat each of the 52 messages corresponded to a different card. Carol can confirm that Alice is not lying about her hand by encrypting the cards with Alices public key and verifying that they are the same as the encrypted messages she sent to her in step (8).
If either Bob or Carol wins, the winner reveals his hand and keys. Alice can confirm that the cards are legitimate by checking her random strings. She can also confirm that the cards are the ones dealt by encrypting the cards with the winners public key and verifying that they are the same as the encrypted messages she received in step (3) or (5).
This protocol isnt secure against collusion among malicious players. Alice and another player can effectively gang up on the third and together swindle that player out of everything without raising suspicion. Therefore, it is important to check all the keys and random strings every time the players reveal their hands. And if youre sitting around the virtual table with two people who never reveal their hands whenever one of them is the dealer (Alice, in the previous protocol), stop playing.
Understand that while this is all interesting theory, actually implementing it on a computer is an arduous task. A Sparc implementation with three players on separate workstations takes eight hours to shuffle a deck of cards, let alone play an actual game .
Attacks against Poker Protocols
Cryptographers have shown that a small amount of information is leaked by these poker protocols if the RSA public-key algorithm is used [453, 573]. Specifically, if the binary representation of the card is a quadratic residue (see Section 11.3), then the encryption of the card is also a quadratic residue. This property can be used to mark some cardsall the aces, for example. This does not reveal much about the hands, but in a game such as poker even a tiny bit of information can be an advantage in the long run.
Shafi Goldwasser and Silvio Micali  developed a two-player mental-poker protocol that fixes this problem, although its complexity makes it far more theoretical than practical. A general n- player poker protocol that eliminates the problem of information leakage was developed in .
Other research on poker protocols can be found in [573, 1634, 389]. A complicated protocol that allows players to not reveal their hands can be found in . Don Coppersmith discusses two ways to cheat at mental poker using the RSA algorithm .
Anonymous Key Distribution
While it is unlikely that anyone is going to use this protocol to play poker via modem, Charles Pfleeger discusses a situation in which this type of protocol would come in handy .
Consider the problem of key distribution. If we assume that people cannot generate their own keys (they might have to be of a certain form, or have to be signed by some organization, or something similar), we have to set up a Key Distribution Center to generate and distribute keys. The problem is that we have to figure out some way of distributing keys such that no one, including the server, can figure out who got which key.
This protocol solves the problem:
Eve, sitting in the middle of this protocol, has no idea what key Alice chose. She sees a continuous stream of keys go by in step (4). When Alice sends the key back to the server in step (7), it is encrypted with her public key, which is also secret during this protocol. Eve has no way of correlating it with the stream of keys. When the server sends the key back to Alice in step (9), it is also encrypted with Alices public key. Only when Alice decrypts the key in step (10) is the key revealed.
If you use RSA, this protocol leaks information at the rate of one bit per message. Its the quadratic residues again. If youre going to distribute keys in this manner, make sure this leakage isnt enough to matter. Also, the stream of keys from the KDC must be great enough to preclude a brute-force attack. Of course, if Alice cant trust the KDC, then she shouldnt be getting keys from it. A malicious KDC could presumably keep records of every key it generates. Then, it could search them all to determine which is Alices.
This protocol also assumes that Alice is going to act fairly. There are things she can do, using RSA, to get more information than she might otherwise. This is not a problem in our scenario, but can be in other circumstances.
|Previous||Table of Contents||Next|