building a true RNG
Ben Laurie
ben at algroup.co.uk
Sun Jul 28 09:38:00 EDT 2002
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 majordomo at wasabisystems.com
More information about the cryptography
mailing list