By the standard security definition of a Pseudo Random Generator, if $G$ is a PRG, then $G'$ such that $G'(0\mathbin\|x)=0\mathbin\|G(x)$ and $G'(1\mathbin\|x)=1\mathbin\|G(x)$ is a PRG. We can build a PRG which output starts by some bits of its input, to some arbitrarily large extent.

This means that feeding a practical source of entropy to a PRG secure by that standard security definition can be very unsafe.

Do we have a stronger security definition of PRG (or some other standard cryptographic construction) that avoids this pitfall, and insure security of the output when the input as some (min)entropy?

Addition: there's nothing wrong with the standard definition of PRG. It is consistent, and useful. It's just not what's needed in some cases, including stretching an imperfect entropy source. I'm asking if we have some stronger security definition of crypto-gismo-with-a-PRG-interface avoiding such issue. Much like for hash we have security in the ROM that's stronger than collision and (first and second) preimage resistance.


1 Answer 1


There is nothing wrong with the definition of PRG. The definition assumes that the seed is uniformly distributed. If this is not the case, and you only have a source with good min-entropy, then you should use a randomness extractor/key derivation function first. The result of this should then be input as the seed, and all will be fine.

  • $\begingroup$ "Randomness extractor" is not quite what I'm looking for: problem is, it is not interface-compatible with a PRG, for it still needs a uniform random secret input by the definition there. Would a hash secure in the ROM, fed with enough bits that the min-entropy reaches a security parameters, then fed to a PRG (with enough expansion that the combination is a PRG) fit? $\endgroup$
    – fgrieu
    Dec 3, 2018 at 17:18
  • $\begingroup$ @fgrieu There are notions of "seedless extractors" which you may find interesting. Though they do require special properties of their randomness sources, for example for "extractors for independent weak random sources" that require several (at least two) sources and require that they are independent. $\endgroup$
    – Maeher
    Dec 3, 2018 at 18:16
  • $\begingroup$ Heuristically, hashing the seed is good enough. In the ROM, this is secure. $\endgroup$ Dec 4, 2018 at 12:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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