building a true RNG

[David Wagner]

> To test a hash function h() whose range is S,
> let F be the set of "balanced" functions from S -> {0, 1}.  (Balanced
> meaning that each f in F maps exactly half of S to 0 and half to 1.)
> If you can contrive to choose many members of F at random, and compose
> them with h for many arguments of h, you should be able to set
> confidence limits on how much of S is covered by h.

Can you elaborate?  What would the computational complexity of this be?

Estimating the size of {x : f(h(x))=1} to within relative error e
requires O(1/e^2) evaluations of h, if I understand correctly.  If we
consider the difference between a hash function that can hit all of
S, and another hash function that misses only one element of S, we'll
need to resolve the size of these sets to within relative error 1/|S|.
That suggests we'll need |S|^2 evaluations of h, which is infeasible
for SHA1 and slower than the naive O(|S|) algorithm.

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