David Wagner wrote: > 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.
That's the kind of thing mathematicians like to say - but how much does it apply to the real world? For example, you can't produce your example set for SHA-1 or MD5, can you? If you are prepared to factor in cost, then the landscape changes, I would contend. Mathematicians generally assume uncountable resources. Even constructivists assume countable resources. However, we can assume _finite_ resources. Big difference. Cheers, Ben. -- http://www.apache-ssl.org/ben.html http://www.thebunker.net/ Available for contract work. "There is no limit to what a man can do or how far he can go if he doesn't mind who gets the credit." - Robert Woodruff --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]