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 problem can be described thus: "How can one allow only authorized actors to have access to certain information while not using a trusted arbiter?"
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".
The concept of multi-player mental poker was introduced in Moti Yung's 1984 book Cryptoprotocols.
One possible algorithm for shuffling cards without the use of a trusted third party is to use a commutative encryption scheme.
The encryption scheme used must be secure against known-plaintext attacks: Bob must not be able to determine Alice's original key A (or enough of it to allow him to decrypt any cards he does not hold) based on his knowledge of the unencrypted values of the cards he has drawn.
This rules out some obvious commutative encryption schemes, such as simply XORing each card with the key.
It has been used to implement a secure version of the German card game Skat, achieving modest real-world performance.
To date, mental poker approaches based on the standard Alice-Bob protocol (above) do not offer high enough performance for real-time online play.
As a result, this method is uniquely useful in poker-style games, in which the number of cards dealt is very small compared to the size of the whole deck.
However, the method needs all cards that have already been dealt to be known to all, which in most poker-style games would beat its very purpose.
In other words, given E(c1) and E(c2), it must be possible to answer whether c1=c2, without the players learning any other information (specifically, the identities of c1 and c2).
As a result, this scheme turns out to be 2-4 times faster (as measured by the total number of modular exponentiations) than the best-known protocol [JAK99] that does full shuffling using mix-networks.
However, by making limited assumptions about the trustworthiness of third parties, significantly more efficient protocols may be realized.
The protocol for choosing cards without shuffling may be adapted so that the encryption is handled by two or more servers.
Furthermore, because players ultimately decide which cards are dealt, non-trustworthy servers are unable to influence the game to the extent that is possible in traditional online poker.
Finally, step one in the protocol may be done offline, allowing for large numbers of shuffled, encrypted "decks" to be pre-computed and cached, resulting in excellent in-game performance.