The Previous discussion can be found
[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
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.
[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
- [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.
does it work?
[
HalFinney] wrote: Yes, I think it is fair (but it's not a
[shuffle.])
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.
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
[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:
plaintext = sharedtext (250chars) string add to usertext (250chars) = 500chars 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.
Cryptographic Pseudo-Random Number Generators
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
[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.
(from an old thread) [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 (int i = 51; i >= 0; i--) swap(deck, i, arr[i]);
(your new thread here)
CategoryCryptography