Editing revision 11 of ProtocolReviews
HomePage
|
RecentChanges
|
Preferences
Editing old revision 11. Saving this page will replace the latest revision with this text.
The Previous discussion can be found [http://www.toothycat.net/wiki/wiki.pl?DouglasReay/FairDice here]. Please continue the discussion now in this DiscussionArea on this page below: Where text has been copied here from email (with the senders permission) my apologies if I have messed up your formatting anywhere. Thanks. --DouglasReay * [http://fairdice.sourceforge.net/cgi-bin/discuss.pl?ProtocolReviews#thread1 Thread 1] - why have a sharedtext? * [http://fairdice.sourceforge.net/cgi-bin/discuss.pl?ProtocolReviews#thread2 Thread 2] - does it work? * [http://fairdice.sourceforge.net/cgi-bin/discuss.pl?ProtocolReviews#thread3 Thread 3] - which hash algorithm to use? * [http://fairdice.sourceforge.net/cgi-bin/discuss.pl?ProtocolReviews#thread4 Thread 4] - best length for the plaintext? * [http://fairdice.sourceforge.net/cgi-bin/discuss.pl?ProtocolReviews#thread5 Thread 5] - Cryptographic Pseudo-Random Number Generators * [http://fairdice.sourceforge.net/cgi-bin/discuss.pl?ProtocolReviews#thread6 Thread 6] - shuffling * [http://fairdice.sourceforge.net/cgi-bin/discuss.pl?ProtocolReviews#thread7 Thread 7] - (your new thread here) ---- [#thread1] = why have a sharedtext? = [HalFinney] wrote: I don't see that sharedtext plays much of a role here. It is the 64 bits of usertext which is providing privacy. Everyone knows sharedtext so there is no particular advantage from it. : DouglasReay wrote: If we just took the digest of a usertext the user could totally specify, they could spend years in advance finding 2 usertexts that gave the same digest. :By including a sharedtext that includes information like the time, this makes it much much harder for the user to predict in advance what sharedtext they need to find usertexts for to give collisions. And even if they do find a collidng pair, it prevents re-use. ::[HalFinney] wrote: Okay, that's a good idea. [http://www.toothycat.net/wiki/wiki.pl?PaulCrowley PaulCrowley] wrote: # The house publishes a list of parties (including itself) # All parties privately choose a random seed # All parties reveal a hash of their seed # All parties except the house reveal their seeds # The house hashes all seeds including its own in the order of the list published : DouglasReay wrote: 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 :: [http://www.toothycat.net/wiki/wiki.pl?MoonShadow MoonShadow] wrote: 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? ::: DouglasReay wrote: revealing the seeds one bit at a time sounds nice, but I'm not sure it could be done efficiently enough in practice over the internet between multiple players. It would certainly make tunneling over email problematic. ---- [#thread2] = does it work? = [HalFinney] wrote: Yes, I think it is fair (but it's not a [http://fairdice.sourceforge.net/cgi-bin/discuss.pl?ProtocolReviews#thread6 shuffle.]) ---- [#thread3] = which hash algorithm to use? = [HalFinney] wrote: Should you negotiate a hash? I don't know what to say about hashes right now. I don't think negotiation is that good an idea for these kinds of protocols, but everything is up in the air at the moment. Most people that I've talked to think Tiger has had insufficient cryptanalysis to be trusted at this point, although it will probably start getting more attention now that so many hashes are in trouble. :DouglasReay wrote: Points in favour of multiple hashes: Some people won't consider an algorithm unless it uses a known quantity such as MD5. Some people won't consider an algorithm unless is doesn't use MD5. :DouglasReay wrote: Points against multiple hashes: i a 3 or more participant game Player 1 will want to verify that Player 2's revealed plaintext matches their previously revealed digest of it - which means that if Player 1 and the Host negotiate Algorithm X and Player 2 and the Host negotiate Algorithm Y, there is a problem. ---- [#thread4] = best length for the plaintext? = [HalFinney] wrote: It's not clear to me from your description what exactly the input is to the hash function. I think it's the sharedtext concatenated with the usertext, where the usertext is basically a random 64 bit quantity. (In your [http://www.google.com/groups?selm=5bx*vZSsq%40news.chiark.greenend.org.uk&output=gplain sci.crypt posting] you said 1000 bits, which is more than necessary.) Then when they all open their inputs, you take the 64 bit usertexts modulo numberOfOutcomes to get the inputs which are all added up (again mod numberOfOutcomes) to get the result. :[DouglasReay] wrote: <CODE>plaintext = sharedtext (250chars) string add to usertext (250chars) = 500chars</CODE> where chars are hex (0123456789ABCDEF) carrying 4 bits info [HalFinney] wrote: I might go a little bigger than 64 bits here, but not as big as 1000. I think the crypt21 project I told you about used 160 bits. For the sizes, as I said above, somewhere between 64 and 1000 will be a good medium. I might go a little bigger than 160 if you really think this will be in use years from now. The next logical size would be either 192 or 256. I really don't think it matters much once you are in this range. ---- [#thread5] = Cryptographic Pseudo-Random Number Generators = ---- [#thread6] = shuffling = [HalFinney] wrote: Card shuffling is a harder problem because the probabilities must change with every card, and some cards aren't shown to everyone. You might want to take a look at [http://sourceforge.net/projects/crypt21 crypt21] which also has some code to implement fair dice rolling and card shuffling. :[DouglasReay] wrote: Fairdice shuffles a deck by generating a random number then translating that to a particular deck. The casino tells each player what card they have as the desk is dealt. At the end of the game, the players can use the earlier revealed hashes to confirm the casino did use the fairly shuffeled deck. ::[HalFinney] wrote: Yes, that will work for a game like, say, blackjack, where all the players' cards are revealed. :[DouglasReay] wrote: I have one participant (the casino or 'host') who does get to see all the cards. It is not symmertric. ::[HalFinney] wrote: Yes, the crypt21 card system is designed for games like poker where it is important that uncalled bluffs never get exposed, so that players don't learn more than they should about other players' bluffing strategy. It uses a very complicated (and slow) algorithm to shuffle the deck. ::The basic idea is to create an ElGamal public key whose private part is shared among all the players, then to encrypt the cards to that public key. To shuffle, each player in turn randomly permutes the cards and re-encrypts each one, then proves (this is the hard part) that they have behaved correctly. Then to expose a card the players cooperate to decrypt it. :::[DouglasReay] wrote: If you have a host who is acting as the dealer but not actually playing a hand themselves, and who is allowed to see the betting strategies, then could one do the shuffle as 52 seperate fairdice generations, and at the end of the game have the host reveal its usertexts only for those cards that got revealed during play? ::::[HalFinney] wrote: Hmmm, I'd have to think about that. There might be a way to do it, but it's not clear. The problem is that some cards get revealed only to one player, and I can't see how to let the dealer show that he is behaving properly in the general case where there is partial information about the cards. If you have any ideas along this line I'd love to hear them (from an old thread) [http://www.toothycat.net/wiki/wiki.pl?PeterTaylor 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. 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 <CODE>(int i = 51; i >= 0; i--) swap(deck, i, arr[i]);</CODE> ---- [#thread7] (your new thread here) ---- CategoryCryptography
Summary:
This change is a minor edit.
(Visit
Preferences
to set your user name.)