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