building a true RNG

[David Wagner]

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 majordomo at wasabisystems.com