www.vitenka.com | ToothyWiki | Vitenka | RecentChanges | Login | Webcomic

Based on DouglasReay/FairDice

This is such a nastier problem.  The first step; revealing a card from the deck to both players is simple enough.  Roll a die exactly as per DouglasReay/FairDice and look down the list of cards, skipping those already drawn.

Revealing a card to only one player is also relatively easy - go as per DouglasReay/FairDice except one player omits the last step, and does not reveal the number they chose - only a signed-then-crypted message with it (plus salt).  That way, they see all the numbers, and thus the card - and everyone else does not, but has something that can be used as proof of the card (in case that player then needs to show it, and later prove they showed the right one).

So much for the relatively obvious parts.  Now - having revealed a card to only one player; reveal a second card to a second player.  For example, consider the simple game:
Each player draws a card off the top of the deck, looks at it, then bets (with raises etc.) whether they have the higher card.
We'd really like to implement something that simple without resort to a trusted third party!

But the challenge is - once the first card is chosen, picking the second card needs to ensure it cannot pick the same card; but without giving away wht that is to the other player.

The best I can see is this:

Players jointly choose salt; and a one-way hash function (key).  Effectively, a private key for which no public key is known.

They then generate a 'top card' as above.  Now, to prove that they are not the same card - each player adds the shared-salt, and crypts the card that they chose with the joint key.  And shares the result.  If the results are the same, then so must the source card have been; go back and try again.

This can be extend to drawing yet more cards; but yeuch that's a lot of transactions for each card draw!

And, worse, unless the deck is really large; it's a simple dictionary attack to break it.

I bet better can be done; what is really needed is a sequence of the deck, with no way to generate the next item without revealing that you've done so (though not revealing what you got).

What we've found particularly fiddly in the past is games that involve passing cards from one player's hand to another, such as drafting Agricola or MtG, Hearts, Go Fish etc. Then Player A needs to give player B a card's identity, but then not be able to tell which of player B's cards is the one that player C took. --AlexChurchill
And indeed, as I recall, the only solutions we've used are either a trusted mediator (human or electronic (such as PyDraft)), or re-hashing at each step. --CH

www.vitenka.com | ToothyWiki | Vitenka | RecentChanges | Login | Webcomic
This page is read-only | View other revisions | Recently used referrers
Last edited March 2, 2017 4:01 pm (viewing revision 3, which is the newest) (diff)