[Theory] UC Theory Seminar

[Alexander Razborov]

%%%%%%%%%%% NOTE NON-STANDARD DAY AND ROOM %%%%%%%%%%

Departments of Mathematics & Computer Science
Combinatorics & Theory Seminar

Thursday, OCTOBER 3
John Crerar Library 390 @3:30pm

Yevgeniy Dodis (NYU)
New York University

Title: Seedless Fruit is the Sweetest: Random Number Generation, Revisited

Abstract: 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 primitive can be kept independent of 
the source.

Our work 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 that the source 
produces sufficient entropy even given its evaluations of the underlying 
primitive. We also provide natural practical provably-secure 
constructions based on hash-function designs from compression functions, 
block ciphers, and permutations.
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 ever-lasting security.

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