[Theory] UC Theory Seminar: a reminder

[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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20191002/b91f6fa9/attachment.html>