Paper 2019/198

Seedless Fruit is the Sweetest: Random Number Generation, Revisited

Sandro Coretti, Yevgeniy Dodis, Harish Karthikeyan, and Stefano Tessaro


The need for high-quality randomness in cryptography makes random-number generation one of its most fundamental tasks. A recent important line of work (initiated by Dodis et al., CCS ’13) focuses on the notion of *robustness* for *pseudorandom number generators (PRNGs) with inputs*—these are primitives that use various sources to accumulate sufficient entropy into a state, from which pseudorandom bits are extracted. Robustness ensures that PRNGs remain secure even under state compromise and adversarial control of entropy sources. However, the achievability of robustness inherently depends on a seed, or, alternatively, on an ideal primitive (e.g., a random oracle), independent of the source of entropy. Both assumptions are problematic: seed generation requires randomness to start with, and it is arguable whether the seed or the ideal primitive can be kept independent of the source. This paper resolves this dilemma by putting forward new notions of robustness which enable both (1) *seedless* PRNGs and (2) *primitive-dependent* adversarial sources of entropy. To bypass obvious impossibility results, we make a realistic compromise by requiring that the source produce sufficient entropy even given its evaluations of the underlying primitive. We also provide natural, practical, and provably secure constructions based on hash-function designs from compression functions, block ciphers, and permutations. Our constructions can be instantiated with minimal changes to industry-standard hash functions SHA-2 and SHA-3, or HMAC (as used for the key derivation function HKDF), and can be downgraded to *(online) seedless randomness extractors*, which are of independent interest. On the way we consider both a *computational* variant of robustness, where attackers only make a bounded number of queries to the ideal primitive, as well as a new *information-theoretic* variant, which dispenses with this assumption to a certain extent, at the price of requiring a high rate of injected weak randomness (as it is, e.g., plausible on Intel’s on-chip RNG). The latter notion enables applications such as everlasting security. Finally, we show that the CBC extractor, used by Intel’s on-chip RNG, is provably insecure in our model.

Available format(s)
Publication info
Preprint. Minor revision.
pseudo-randomnesssymmetric cryptographyprovable securityentropy accumulationPRNG with input
Contact author(s)
karthik @ cs nyu edu
2019-03-25: last of 2 revisions
2019-02-27: received
See all versions
Short URL
Creative Commons Attribution


      author = {Sandro Coretti and Yevgeniy Dodis and Harish Karthikeyan and Stefano Tessaro},
      title = {Seedless Fruit is the Sweetest: Random Number Generation, Revisited},
      howpublished = {Cryptology ePrint Archive, Paper 2019/198},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.