Note: this version includes a fixed “flaw” that the author is no longer sure needs “fixing”. It might be a perfectly fine solution without the computed “adjustments”.
http://en.wikipedia.org/wiki/Mental_poker
Any mental poker protocol that relies on the players to perform the encryption is bound by the requirement that every player encrypt every card that is dealt. 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. Under the assumption that the servers are non-colluding, such a protocol is secure.
The basic protocol using two servers is as follows:
- Servers S1 and S2 encrypt and shuffle a deck of cards, and publish a non-malleable commitment to some permutation of encrypted cards to the players. This can be done with any of several well-understood cryptographic protocols.
- Players compute independent random numbers in {0,…,51}, which are combined to generate a random number in {0,…, 51}, as in [GOL05]
- The random number is used as an index into the random permutation, the appropriate player gains “ownership” of the specified card, and the servers send that player the keys to read the card’s value.
In this protocol, servers S1 and S2 must collude if either is to learn the values of any cards. 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. The scheme may be extended to allow more servers, (and thus, increased security), simply by including the additional servers in the initial encryption. 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.
Players have a universally ordered “cheat sheet” of all possible permutations of a deck of cards. Each permutation has a number from 1 to 52!. We call a “state” a certain permutation or order of cards.
Each player secretly picks a random number, and puts it into the function. Each individuals’ choice corresponds to a certain 52 card permutation (state) from the cheat sheet. The function adds the numbers revealing the sum only to itself. This sum gives a number that corresponds to a certain deck state. This deck state is the permutation of cards the players will use for the game (the order the cards lie in the deck).
Once the function knows the deck state it can then compute an “adjustment” key (explained below) for each card in the deck. The adjustment key is 52 adjustments the players will need to apply to the “cheat sheet” in order to reveal (“decrypt”) a card.
To reveal a card to the community each player gives their own corresponding card from the initial random number they chose. If a player is to draw a card that others shouldn’t see, she simply collects all other players “key” card but doesn’t reveal her own.
Example:
2 players are HU with a 3 card deck (Q K A)
P1 chooses random number 2 (deck state A K Q)
P2 chooses random number 3 (deck state K A Q)
Function computes 2 + 3 = 5
Function computes deck 6 with inputs 2 and 3 gives output K,Q, Q
P1 and P2 know the adjustments are K Q Q
P1 chose number 2 which is deck state A K Q
P2 chose number 4 which is deck state K A Q
To reveal the first card in deck 6:
P1 gives P2 card 1 A (from deck state 2 ; A K Q)
P2 gives P1 card 1 K ( from deck state 3; K A Q)
Adjustment card 1 K (from adjustment output K Q Q)
(Q=1, K=2, A=3)
A + K + K = Q
3 + 2 + 2 = 2
Q is the first card in the deck.
Notes: below are some notes on some unfinished thoughts, readers can largely ignore them for now
1 A B C
2 A C B
3 B A C
4 B C A
5 C A B
6 C B A
1 (1-6)
2 (1-6)
….
6 (1—6)
1.1 = A C B
1.2 = B A C
….
1.6 = ABC
2.1 = BAC
2.2 = BCA
…
2.6 = ACB
6.1 = ABC
6.2 = ACB
…
6.6 = CBA
thewealthofchips 