building a true RNG

[David Wagner]

> However, what we're working with in the case of a typical RNG isn't
> functions between finite buffer-fulls of data, but functions between
> infinite sets of entire bitstreams which need to be implemented within a
> finite memory constraint. Whatever the algorithm, it can have state.

That obviously can't help.  Introducing the notion of streams of data
can't make the problem any easier.  Just look at the first n bits of
output; they are going to be a deterministic function of the first n' bits
of input, and we can simply let f be the function mapping the first n'
bits of input to the first n bits of output.  (Or, the function mapping
the entire input stream to the first n bits of output.)  Then we're back
to the same problem: since there is no way to guarantee that the first
n bits of output will be uniform if the input distribution is arbitrary,
there is no way to solve the streaming problem, either.

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at wasabisystems.com