On 10/24/2008 03:40 PM, Jack Lloyd wrote: > Perhaps our seeming disagreement is due to a differing interpretation > of 'trusted'. I took it to mean that at least one pool had a > min-entropy above some security bound. You appear to have taken it to > mean that it will be uniform random?
Thanks, that question advances the discussion. The answer, however, is no, I did not assume 100% entropy density. Here is the critical assumption that I did make: We consider the scenario where we started with N randomness generators, but N-1 of them have failed. One of them is still working, but we don't know which one. 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. Here _trusted_ means we have a provable lower bound on the entropy. I assume this is the same as the aforementioned "min-entropy above some security bound". We next consider the case where N-1 of the generators have failed, or can no longer be trusted, which is essentially the same thing for present purposes. Now we have N-1 generators putting out zero bits of trusted entropy, plus one generator putting out 80 bits of trusted entropy. I emphasize that these 80 bits of trusted entropy are necessarily uncorrelated with anything happening on the other N-1 machines, for the simple reason that they are uncorrelated with anything happening anywhere else in the universe ... otherwise they would not qualify as trusted entropy. XORing together all N of the 160 bit output words produces a single 160 bit word containing 80 bits of trusted entropy. Therefore, unless there is some requirement or objective that I don't know about, the previously-stated conclusion holds: >> XOR is a good-enough combining function, >> and nothing else would be any better. XOR is provably correct because it is _reversible_ in the thermodynamic sense. That means it cannot increase or decrease the entropy. ============= Obviously this numerical example generalizes to any entropy density from zero to 100% inclusive. To summarize: The key assumptions are that we have N-1 broken generators and one working generator. We don't know which one is working, but we know that it is working correctly. For more about the theory and practice of high-entropy randomness generators, see http://www.av8n.com/turbid/ --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
