[11228] in cryptography@c2.net mail archive
Re: building a true RNG
daemon@ATHENA.MIT.EDU (Ben Laurie)
Mon Jul 29 10:51:50 2002
Date: Sun, 28 Jul 2002 14:38:00 +0100
From: Ben Laurie <ben@algroup.co.uk>
To: David Wagner <daw@mozart.cs.berkeley.edu>
Cc: cryptography@wasabisystems.com
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@wasabisystems.com
