John Denker <[EMAIL PROTECTED]> wrote: > To say the same thing in more detail: Suppose we start > with N generators, each of which puts out a 160 bit word > containing 80 bits of _trusted_ entropy. That's a 50% > entropy density.
So you need a 2:1 or heavier compression that won't lose entropy. If you just need one 160 word out per N in, then hashing them is the obvious way to do that. > We next consider the case where N-1 of the generators have > failed, or can no longer be trusted, ... > XOR is provably correct because it is _reversible_ in the > thermodynamic sense. That means it cannot increase or > decrease the entropy. Yes, but the proof holds for any reversible mapping. XOR makes each output bit depend on exactly two inputs bits. Sometimes you want a mapping that mixes them better. If one input is entirely random, XOR is fine; random ^ x is random for any x. It is also fine in the case above, where only one generator works. If > 1 inputs have some entropy but none have enough, which seems to me the commonest case, XOR is not the best choice; it does not mix well enough. Nyberg's perfect s-boxes are in some ways the ideal mixer. 2n bits in, n out, all columns and all linear combinations of columns are bent functions. Big S-boxes are expensive though, and building even small Nyberg S-boxes is going to take significant effort. Designing something that uses a bunch of say 8 by 4 S-boxes to do good mixing on 160-bit chunks is not trivial either. You could use IDEA multiplication in mixing. Two 16-bit words in, one out, and every output bit depends on all input bits. If every 16-bit input word has 50% entropy density (not the same as every 160-bit word does, but perhaps close enough) then the output should have 100%. For N > 1, you need to combine those and worry about overall mixing. If entropy density is known to be ~50%, you can combine pairs with IDEA to get ~100%, then use cheaper operations for any other mixing needed. I'd use addition, which costs about the same as XOR but gives slightly better mixing because of carries. For N > 2 and density < 50%, you could use a cascade of IDEA operations 8->4->2->1 or whatever. Or do something like: combine two 160-bit chunks with 10 IDEA multiplications, circular shift the result 8 bits, combine with next 160-bit input, ... At some point, you may find yourself designing a hash. If that happens, just give up and use a standard hash. -- Sandy Harris, Quanzhou, Fujian, China --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]