combining entropy

[John Denker]

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 majordomo at metzdowd.com