One question in cryptography that took years to settle was the problem of mental poker: can a group of mutually distrusting people play poker over the phone with confidence that no one can cheat?

Admittedly, the question seems bizzare at first glance. However this is typical of the sort of problem that cryptographers like to pose to each other. Think about it for a moment. How could you even deal cards fairly over the phone? The question of mental poker turns out to have implications for more general classes of cryptographic tasks, so this question isn't purely a flight of fancy.

The first results came in the late 70's when Rivest, Shamir, and Adleman (yes the very same RSA) show that the task is impossible from the point of view of information theory. However this doesn't mean that we can't actually do it in practice. In fact, in the same paper they gave a scheme that seemed to achieve the goal based on some reasonable assumptions.

Unfortunately for everyone, this scheme turned out to be flawed; a player could determine the color of his adversary's cards. Goldwasser and Micali responded with a more secure scheme, but it only works for two players.

Getting closer to the goal, Barany and Furedi devised a solution that works for multiple players. But then a new wrinkle was introduced: what if two or more of the players can form a "team" and work in concert to try to cheat the other players? The Barany-Furedi protocol turns out to be vulnerable to this sort of collusion.

The question was prety much settled by the late 80's: if you can make some reasonable assumptions about number theory or if you have a trusted 3rd party to "shuffle" the "cards" for you, it can be done.

But that doesn't mean it is easy. You can't do the type of math involved on the back of a napkin. In fact, even using fairly fast computers there is evidence to suggest that it would be one of the slowest poker games ever: it takes dozens of minutes just to "shuffle" the "cards."

The bottom line: an interesting thought experiment but if you ever feel the need to play poker with people you don't know and don't trust over the phone, you should probably go back on your medication.

Playing poker over the phone with people you don't trust is probably a bad idea.

Log in or register to write something here or to contact authors.