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 [EMAIL PROTECTED]