A Shamir, Ronald L. Rivest and L Adleman, in their paper “Mental Poker” credit Robert W. Floyd with the first proposal of what is known as the Mental Poker problem:
Can Two potentiality dishonest players play a fair game of poker without using any cards-for example, over the phone?
SRA, as they are commonly known, first start out with a proof that such a solution is NOT possible before going on to show how such a solution IS possible given a new twist-encryption technology (ie computers!).
Skipping some basic cryptography lessons the encryption solution is quite basic in metaphor:
Alice “locks” or “hides” the value of the cards before she randomly passes them to Bob.
Bob “locks” or “hides” the values of the cards he receives from Alice and passes them back in random order.
Alice requests keys from Bob to the cards she needs to reveal to herself, and she gives keys to Bob for cards he or both of them wish to see together.
The proof and solution is quite nice, except for one fatal flaw: players MUST reveal their strategies at the end of the game in order to detect cheating. In other words the original problem is solved, but we still cannot play poker in this fashion.
Improvements on this protocol were further made by Claude Crepeau. In his paper A Secure Poker Protocol that Minimizes the Effect of Player Coalitions Crepeau makes a point about what requirements are needed for a realistic implementation of a theoretical mental poker solution:
- Uniqueness of cards
- Uniform random distribution of cards
- Absence of trusted third party
- Cheating detection with a very high probability
- Complete confidential of cards
- Minimal effect of coalitions
- Complete confidentially of strategy
Crepeau points out in the introduction that:
Although SRA proved in the two player case that such a solution is not possible from an information theoretic point of view, such solutions might be possible when the players’ computational power is limited. The leakage of partial information found by Liption, in the initial SRA protocol was fixed by Goldwasser & Micali, in the two players case, using probabilistic encryption. Unfortunately this scheme did not extend to a larger number of players. No complete solution to the multi-players version of the problem is yet known.
He introduces 4 functions as well as a selection by each player of a permutation of the deck:
The main improvement of this protocol is protection against coalition. If some players form a coalition, they will not get any advantage from it, other than learning each other’s hand.
Interestingly the new protocol proposed can seemingly handle “…almost any card game, as well as games, such as Scrabble.” A card exchange protocol, a discard protocol, and a card return protocol are all defined.
However we are still left with a problem for implementation, for practical use, because:
The strategy of each player is completely revealed at the end of the game… Although we believe such a protocol can be achieved, we do not have a complete solution yet.
Fortunately Crepeau has an answer for this problem as well as he describes in his paper A zero-knowledge Poker protocol that achieves the confidentiality of the players’ strategy or How to achieve an electronic Poker face.
Crepeau claims:
This paper proposes a new poker protocol that allows players to keep secret their strategy… It achieves all the necessary conditions suggested in [A Secure Poker Protocol that Minimizes the Effect of Player Coalitions]
The emphasis here is on the solution to:
- Complete confidentially of strategy
Crepeau makes use of an All-or-nothing disclosure of Secrets (ANDOS) protocol that allows Bob to request the information needed to decipher a card, without Bob tricking Alice into revealing any information about any other cards. This negates any reason to reveal strategies at the end of the game. (Here is a possible updated version of such a protocol)
Crepeau’s final protocol implementation looks like this:
He concludes:
We have achieved the first complete solution to the mental poker problem. Our solution cumulates all the conveniences of a real poker game and the elimination of the unfortunate human factor (from a strategic point of view).
However as of yet there still hasn’t been a fully realized implementation of this solution for various reasons as described in the next section A Relevant Overview of Mental Poker Implementations
thewealthofchips 