# Generating shared secret random permutation

There are three blind card game players. Each player does not trust any other, even prejudicing other two players may not be blind, or there may be others in the room, peeking at their cards.

In order to protect from glimpsing their hands, each player puts each of his cards into separate locked box, each box having its own key. Owners know which box holds which card, while others don't. In other words, players make a HMAC-SHA256 hashes of strings in form 'card_value:commonly_agreed_public_salt' with random key for each card, and then announce each other list of the hashes they posess.

When player makes a move, he moves one of locked box he owns to the middle of table and discloses the key, so everyone sees what card is inside. In other words, when making a move, player discloses HMAC key used to hash card value, and card value itself. This way other players can verify that this card was really owned by him.

I hope this approach makes it impossible for all the observers in the room, if any, to get any information, other than count of cards in posession of each player, am I missing something?

Now I'm stuck in how should I design retrieval of additional or initial cards from deck. I guess I should make use of preseeded PRNG similar to Mersenne Twister, to avoid duplicates, but how to make seed both secret, so one cannot simply traverse all the deck to know all the cards in the future, or to know which cards were picked by other players, and shared, so everyone will get same results while grabbing cards from deck.

Any ideas on this?

-
Are you familiar with Mental Poker? en.wikipedia.org/wiki/Mental_poker –  bmm6o Mar 28 '14 at 14:41

Your approach makes getting information other than count of cards in
possession of each player at least as hard as breaking the PRFness of HMAC.

To make it information-theoretically impossible "for all the ... each player",

$\;\;$ if different card_values have different lengths then use
$\;\;$ SHA256(commonly_agreed_public_salt:card_value)
$\;\;$ instead of card_value for what follows

$\;\;$ at the beginning, each player chooses a strong extractor whose output length is equal to the length of
$\;\;$ each card_value, chooses a random seed for that extractor, and sends both of those to everyone
$\;\;$ (those choices can be reused)

$\;\;$ players compute SHA256(commonly_agreed_public_salt:secret_random_value)
$\;\;$ and Extract(secret_random_value,seed) xor card_value
$\;\;$ with independently chosen secret_random_value for each card,
$\;\;$ and then announce to each other the list of the pairs they possess

.

For retrieval of additional cards from the deck, you need to use
multi-party computation; specifically mental poker protocols.
I've read your answer several times, and now I hope I mostly understood it. To your opinion, is Extract(value, seed) := SHA256(seed:value) with seed being at least 512 bit, applicable? –  modchan Mar 28 '14 at 15:41
In my opinion, it's not, since part of the point is that the hiding property should be unconditional. $\:$ By following this proof of the Leftover Hash Lemma, one can see the (non necessarily cryptographic) hash family $\:$ (continued ...) $\;\;\;\;$ –  Ricky Demer Mar 28 '14 at 16:01
(... continued) $\:$ only needs to be universal (not necessarily pairwise independent), so one can let Extract(value,seed) be a truncation of left_half_of_value + (right_half_of_value * seed) where + and * are over a finite field. $\;\;\;\;$ –  Ricky Demer Mar 28 '14 at 16:02
In my previous comment, "a truncation" should be replaced with "the least significant bits". $\hspace{.89 in}$ –  Ricky Demer Mar 28 '14 at 16:32
If you use a field with 2^n elements, then you can split value into two halves arbitrarily (or swap left and right halves). $\:$ If you use a field with 2^n elements and directly split value, then there's no point in using a mask, since you would already have the two halves $\:$ If you use a field with p elements, then you should split value according to how it was chosen (as I mentioned in my previous comment), although you can swap left and right halves. $\;\;\;\;$ –  Ricky Demer Mar 29 '14 at 17:56