Mental poker (nonfiction)
Mental poker is the common name for a set of cryptographic problems that concerns playing a fair game over distance without the need for a trusted third party. The term is also applied to the theories surrounding these problems and their possible solutions. The name comes from the card game poker which is one of the games to which this kind of problem applies. A similar problem is flipping a coin over a distance.
The problem can be described thus: "How can one allow only authorized actors to have access to certain information while not using a trusted arbiter?". (Eliminating the trusted third-party avoids the problem of trying to determine whether the third party can be trusted or not, and may also reduce the resources required.)
In poker, this could translate to: "How can we make sure no player is stacking the deck or peeking at other players' cards when we are shuffling the deck ourselves?". In a physical card game, this would be relatively simple if the players were sitting face to face and observing each other, at least if the possibility of conventional cheating can be ruled out.
However, if the players are not sitting at the same location but instead are at widely separate locations and pass the entire deck between them (using the postal mail, for instance), this suddenly becomes very difficult. And for electronic card games, such as online poker, where the mechanics of the game are hidden from the user, this is impossible unless the method used is such that it cannot allow any party to cheat by manipulating or inappropriately observing the electronic "deck".
Several protocols for doing this have been suggested, the first by Adi Shamir, Ron Rivest and Len Adleman (the creators of the RSA-encryption protocol).
One possible algorithm for shuffling cards without the use of a trusted third party is to use a commutative encryption scheme. A commutative scheme means that if some data is encrypted more than once, the order in which you decrypt this data will not matter.
To date, mental poker approaches based on commutative schemes don't offer high enough performance for real-time online play. The requirement that each player encrypts each card imposes a substantial overhead.
A recent paper by Golle [GOL05] describes a mental poker protocol that achieves significantly higher performance by exploiting the properties of the poker game to move away from the encrypt-shuffle model. Measured in terms of the number of single-agent encryptions, the algorithm in [GOL05] is optimal when no collisions occur, in the sense that any protocol that is fair to every player must perform at least as many encryption operations. At minimum, every agent must encrypt every card that is actually used. Otherwise, if any agent doesn't participate in the encryption, then that agent is susceptible to being cheated by a coalition of the remaining players. Unknown to the non-encrypting agent, the other agents may share the keys to enable them all to know the values of all the cards. Thus, any approach relying on the agents to perform the encryption must focus on schemes that minimize the effect of collisions if they are to achieve better performance.
In the News
Fiction cross-reference
Nonfiction cross-reference
External links:
- Mental poker @ Wikipedia