The heading tells everything. Any proof or any kind of reference is welcome regarding this:
Can we get more randomness from a deterministic random bit generator than the entropy that we feed to the generator?
1
-
2$\begingroup$ The correctness of the assertion obviously pivots around how "more randomness" is defined. In the framework of Kolmogorov complexity, and when we consider the DRBG public, we can describe the output sequence of the DRBG as: DRBG(seed), thus the increase in complexity (if any) is minimal and asymptotically negligible [with correction, thanks to @Patriot]. This is not an answer, since that's neither a reference nor a true proof, even in one framework. $\endgroup$– fgrieu ♦Mar 11, 2020 at 18:19
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
Define the Mutual Information of a pair of random variables. $$I(X; Y) = H(X) - H(X\mid Y)$$ For discrete random variables we hae that $H(X\mid X) = 0$, so: $$I(X; X) = H(X)$$
The Data-Procesing Inequality states that for any function $f$, we have that: $$I(f(X); f(Y)) \leq I(X; Y)$$ While we won't need it here, this includes randomized functions, provided they use randomness independent of either $X$ or $Y$. Combining these two, we get that:
$$H(f(X)) - H(f(X)\mid f(X)) \leq H(X) - H(X\mid X)$$ If $f$ is deterministic, I believe the conditional entropies become 0, giving us: $$H(f(X)) \leq H(X)$$ So the output distribution of a DRBG is always lower entropy than the distribution that its seed is drawn from.
-
$\begingroup$ This was really helpful. Thanks a lot sir. @Mark $\endgroup$– R.AliMar 13, 2020 at 4:43