(Please go check I have been fair to you in my re-arrangement of your posts splitting them by subject!) --DR
Vitenka is wondering about extending this to a fair shuffle. The simple case is easy enough: A publishes a shuffle in the form of many signatures to prove it actually said "Card 4 is actually card 18" and then B does the same "Card 18 is actually card 6" and they then co-resolve as the dice addition case.
Where it gets difficult is (in the CCG case) if player B wishes to look at the top card, without showing it to player A. Player A needs to know "B looked at the top card" but to not then know what B saw, nor be able to work it out. And I can't see how to do this. B can't ask "What was card 6?" because then A can work out what B knows, and I can't see an obivous way for B to prove it didn't look at more than it was supposed to. Any ideas? --Vitenka
Interesting. I'd previously thought of the standard fair dice protocol being used to generate a random number between 1 and the number of possible deck shuffles, so the casino could generate a random deck and then prove at the end of the game that the cards it dealt out really had been in accord with the number generated by the players
However this has the problem, in poker, of not being able to prove that part of the deck was random without revealing the rest of the deck and in poker you need to be able to not show your cards at the end of a hand, if your bluff was not called
So I like your (to put in in normal card terms, not magic deck) 'each player generates a mapping of the sorted numbers 1 to 52 to an ordering of the number from 1 to 52; then these get applied one after another'
However, as you say, you need a way so that players during the game don't know which of their 'shuffle fragments' is being used
I suggest having a dealer who also generates a mapping, which is applied first before the players mappings. Then it is ok to Players B to ask A "What is Card 6?", because that will just reveal that to A that B has been passed the 14th card from the dealer's shuffle, not that B has been passed the ace of diamonds.
At the end of the game, the dealer publishes the shuffle fragments only for those cards that have been revealed to everyone--DR
You don't even need that map in the common situation - B can ask A "What is the mapping for the top card (card 1)" and then B has both bits of information, whilst A is unenlightened (except to know that the top card has been seen by B). The difficult bit comes, as you say, when you want to pass a card back. I don't want to have to resort to a trusted third party to hold the final deck mapping, since that person could secretly be the casino and everything explodes again. What I'd really like is to use the "a secret known by x out of y parties" stuf, but I don't know enough about it. I'd like A to be able to release the sdecret mapping to B, without knowing which mapping it has revealed. --Vitenka
Oh, yeah - the protocol needs to agree in advance the order the shuffles will be applied, which means ou can make either the A->B pass invisible, or the B->A pass, but not both. Unless I'm missing something dumb about adding shuffles. --Vitenka
Thinking some more - there's a very limited class of games where this is sufficient. 21 is one - A deals cards to B at B's request, B looks at them, and may then either reveal them to A or keep them hidden forever (and forfeit any pay-out) if they're revealed, A then plays publicly. But it doesn't extent well - and odd things happen if you try to play, for example, bridge, you'd need each player to pass their secrets to the other three - and then if two players collaborate they reveal the entire setup, not just each others hands! More thinking needed I think. --Vitenka
You want to be able to prove part of a deck of cards, while not revealing the cards in hands that players threw in. Would the following scheme work?
1. Start with 52 'card backs'. 2. For each 'card back', generate 52 statements of the form "Card back 1 is not the Ace of Spades", "Card back 2 is not the King of Spades", etc. 3. For each 'card back', select one of its 52 statements to repudiate
Do the above steps collectively in such a way that: A) The dealer can release a statement "Card back 37 is not the Queen of Diamonds" and everyone can check that this statement is valid (ie, it is not a card from another deck), and B) check that the statement isn't the particular statement about 'card back' 37 that was repudiated.
I don't think you even need to do anything that complex for poker - the problems only arise when you need a put a card back into the stack, and have that position forgotten but consistent. With the system above, that back stays marked - a card can't be unrevealed. --Vitenka
Does poker do that? I thought after a hand all the cards went back in and the deck could be re-shuffled?--DouglasReay
I don't believe you always reshuffle after a hand of poker, but that's ok, the discards are on the bottom and you do shuffle before you draw them again. I said I think what you propose is overkill for poker where all you need is a card in the shuffle order to require every player to release their part, and if you discard face down you just don't release your part until after the game. You start to need stuff that complex (and indeed more complex) where such re-anonymisation matters. --Vitenka
PeterTaylor comments that the explanation page should have mentioned the problem of hashing all possible inputs earlier than it did - in fact, before the third party got involved at all.
Xarak may have got the wrong end of the stick but wouldn't it be possible for everyone to just send each other their PGP encrypted vote, and then everyone to reveal their key? Revealing your vote and/or key first would be no disadvantage, and cheating would be impossible ( unless two or more players decided to conspire together, but you can never prevent that. )
DouglasReay responds: Yes, that would work. However the idea is for this to be automated. For a single deck of cards you are likely to do it 51 times. Isn't generating new PGP key pairs a rather slow process?
PeterTaylor observes that you don't need to do it 51 times for a deck of cards. You need to generate one integer in [0, 51!). That's about 220 bits, so if you're using a 256-bit hash it's just one exchange.
Know any good libraries for handling large integers in C? Or for that matter, an algorithm for translating an int between 0 and 52! into a perfectly sorted deck of cards? --DR
(PeterTaylor) Don't really use C. Sorry. The algorithm is just a base change. Divide by 51! to get a number in [0, 51], divide the remainder by 50!, etc. Then with your array arr, and an array deck containing the cards,
for (int i = 51; i >= 0; i--)
swap(deck, i, arr[i]);
I'm confused - I thought this was a long solved problem
Not really. I've come across one company that claims to do something similar. But their implementation is closed source. No one, as far as I am aware, has implemented an open source solution to this. The vast majority of casinos online do not. (Counter examples please?) --DR
Assuming the existence of good one way hashes (which, actually, is hard to assume if you only have two valid messages) you just both sign your messages, send them (ack the replies) and then reveal the keys. Both now have both values, add them modulo and you have a value. You can create the value between as many people as you like - the final value can only be chosen if all players conspire. And, um, if all players are conspiring together then you really don't need this rigmarole ;) --Vitenka
The server also gets to input to the final thing that get's modulo'ed so even a complete player conspiracy should not be able to cheat. --DR
Ok, on deeper reading, it's the number of bits in the plaintext that you are actually fixing. Goodie good. I don't see a problem with the method. The explanation could do with being a bit tider and less mathsy. You've basically made a large number of messages all equivalent ot each other, but with (potentially) different hashes. --Vitenka
One more comment (and I'm truly surprised this hasn't been done before, oh well) - your largest threat is going to be people undermining other parts of your structure. If there is any pattern in the salt that is added (i.e. if your random number generator is crappy) then you'll have a big problem. And it will probably be easiest to refer to the house as just another player (who happens to be hosted on the same server) You might also want to add some stuff to make sure that the same number of people cast votes as you expect to. --Vitenka
And one more, one more comment. Given the posisble gains to a casino of cheating on, say, 1% of rolls to clients who connect fewer than a thousand times - which would be basically undetectable... How big would the hash have to be to make it unlikely that the cheating client doesn't find many clashes in the hash space? --Vitenka
Just sent this (hopefully simpler) protocol to DR:
1) The house publishes a list of parties 2) All parties choose a 160-bit random seed 3) The "house" publishes the hash of its seed 4) All parties reveal their seeds to the house 5) The house publishes all seeds except its own 6) The house hashes all seeds including its own in the order of the list published 7) The result is used to key a CPRNG (say AES-192 in CTR mode) 8) The rolls are generated using this CPRNG using standard algorithms for converting a random bitstream to fair dice rolls (or card selections or whatever) 9) At the end of the game, the house publishes its seed; all parties can verify that the rolls were generated fairly.
This assumes that the "house" is deterministic - ie it doesn't matter that the house gets to know the result of all random rolls at the start of the game, because they don't make any decisions. The house seed must be 160-bits, to avoid key collision attacks. I'm not sure if all parties need 160 bit seeds, but I fear birthday attacks or similar on smaller seeds.--PaulCrowley
(corrected shortly after writing to add step 1, without which the House can choose which hashes to include and in what order)
(PeterTaylor) You still need some way for the house to prove that the seeds it publishes are the seeds it was given. Parties send in {seed, signature(party, seed)} would seem the obvious solution.
Why not amend step 4 to "all parties publish their seeds" and drop step 5? Since the house seed is hashed with everyone else's and is not known until the last step, waiting to generate your seed until everyone else has published theirs does not help you cheat. - MoonShadow
(PeterTaylor) How do I know that you're not also the house?
You don't. You don't care, either. The house committed to its seed in step 3, so can't alter it when the other seeds become known in step 4. *thinks* But the house could reveal its seed to the player before step 4 and the player would then have the required knowledge to pick a good seed. Duh. - MoonShadow
(PeterTaylor) Hmm. That means we want complete hash exchanges before any seed exchanges.
Yes. You're right.
Why would it matter to a player who provided the other seeds? It only matters to a player that their seed is included. And since they will be able to recognise their own seed, no authentication is needed. --DR
It matters because a player could be colluding with the house - the house knows its own seed, so could pick one for the colluding player once it knows everyone else's and publish it when it's publishing the legitimate ones, and the player just say "yes, that's the one I picked". The trick is that you don't want it to be possible for any party to know everyone else's seed before publically committing to theirs. - MoonShadow
Signing won't stop that. A real person could still collaborate with the house. The only way is to use a two part protocol where everyone publishes a hash of their seed before anyone publishes their seed. --DR
So, we have a simpler version: 1) The house publishes a list of parties (including itself) 2) All parties privately choose a random seed 3) All parties reveal a hash of their seed 4) All parties except the house reveal their seeds 5) The house hashes all seeds including its own in the order of the list published 6) The result is used to key a CPRNG (say AES-192 in CTR mode) 7) The rolls are generated using this CPRNG using standard algorithms for converting a random bitstream to fair dice rolls (or card selections or whatever) 8) At the end of the game, the house publishes its seed; all parties can verify that the rolls were generated fairly.
Anyone spot any problems with that?
I'd prefer if people didn't have a completely free choice of random seed, to help prevent them using the birthday-party effect to pre-generate collisions. --DR
Split step 4 up: make all revealing parties reveal their seeds one bit at a time (so everyone's bit 0 are known before any bit 1 are revealed, etc.) This forces you to commit to one of your many precalculated birthday seeds that all hash to the same thing before you know enough of anyone else's to be able to decide which one benefits you most. Hm. The house can still usefully precalculate hash collisions. Maybe use something more resistant to collisions than a crypto hash in order to commit to your seed? What is there? Sign your seed along with a load of salt and publish the signature? Paul, you suggested 160-bit seeds above to resist birthday attacks; how computationally hard is it to find two 160-bit strings that have the same MD5 hash? - MoonShadow
DouglasReay writes: It looks like the decision to go with TIGER not MD5 or SHA was a good one. See [here] and [here] for details. Also [here]
![[Home]](/img/text_logo.jpg){kind=logo}
DouglasReay/FairDice