2
$\begingroup$

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?

$\endgroup$
  • 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 at 18:19
6
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ This was really helpful. Thanks a lot sir. @Mark $\endgroup$ – R.Ali Mar 13 at 4:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.