Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
2  
Are you familiar with Mental Poker? en.wikipedia.org/wiki/Mental_poker –  bmm6o Mar 28 at 14:41

1 Answer 1

up vote 1 down vote accepted

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.
(as already mentioned by bmm6o)

share|improve this answer
    
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 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 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 at 16:02
    
In my previous comment, "a truncation" should be replaced with "the least significant bits". $\hspace{.89 in}$ –  Ricky Demer Mar 28 at 16:32
1  
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 at 17:56

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.