Yevgeniy Dodis (NYU): Seedless Fruit is the Sweetest: Random Number Generation, Revisited

Abstract: 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.

Joint work with Sandro Coretti, Harish Karthikeyan and Stefano Tessaro.