Amir Herzberg wrote: >So I ask: is there a definition of this `no wasted entropy` property, which >hash functions can be assumed to have (and tested for), and which ensures >the desired extraction of randomness?
None that I know of. I'm not aware of much work in the crypto literature on this topic. Actually, there is not much hope for such a property. It is pretty easy to see that, if we make no assumptions on the entropy inputs other than they have sufficient entropy, then no single deterministic algorithm can ever be good at extracting randomness. If we fix any single extraction algorithm A, there exists a distribution D on the inputs which make it give non-uniform output (for example, D might be the uniform distribution on the set {x : A(x) has its first ten bits zero}). This is a standard observation from the theory community's work on derandomization. The only way out of this I can see is to assume we have a small seed of uniformly distributed randomness on the side. This is exactly the direction explored in the theory community in work on extractors, the leftover hashing lemma, and the like. However, from a cryptographic point of view, such an assumption is highly unreasonable (even worse than the "random oracle" assumption). In short: I know of no better way to analyze cryptographic randomness extraction than to use the random oracle model. --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]