building a true RNG

[David Wagner]

John S. Denker wrote:
>I'm talking about a !!hash!! function that doesn't waste entropy.

Out of curiousity, what, precisely, does "doesn't waste entropy" mean?

For instance, do you mean the following?
  Definition.  Let f:X->Y be a function, and assume |X| > |Y|.  When D is a
  distribution, we say that "f doesn't waste entropy on D" to mean that
  the Shannon entropy satisfies H(f(x)) >= min(H(x), lg |Y|), where x
  is a random variable distributed according to D.  Also, we say that
  "f doesn't waste entropy" to mean that, for every distribution D on X,
  it is the case that f doesn't waste entropy on D.
Is that what you meant?

If that definition captures what you meant, then I can prove that no
interesting function satisfies this criteria.  In particular, there is
no function f which doesn't waste entropy, unless |Y|=1.  The proof is
simple enough that you can probably find it with a moment's contemplation,
but let me know if you want to see it.

Or, maybe you consider the entropy condition above too strict.
Maybe you'd prefer to change it as follows:
  Definition.  ... satisfies H(f(x)) >= min(H(x), lg |Y|) - 1, where ...
However, even in this case there is still a strong negative result:
there will be no function that satisfies this condition unless |Y| <= 2.

I hope this illustrates why it is hard to make precise just what
assumptions on the hash function we need to make for our entropy
distillation algorithm to be secure.  This is all pretty standard stuff;
it's just not well-documented in tutorial form in the literature, as
far as I know.

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at wasabisystems.com