
<html><head><meta http-equiv="content-type" content="text/html; charset=utf-8"></head><body dir="auto"><span style="background-color: rgba(255, 255, 255, 0);">%%%%%%%%%%% NOTE NON-STANDARD DAY AND ROOM %%%%%%%%%%<br><br>Departments of Mathematics & Computer Science<br>Combinatorics & Theory Seminar<br><br><a href="x-apple-data-detectors://0" dir="ltr" x-apple-data-detectors="true" x-apple-data-detectors-type="calendar-event" x-apple-data-detectors-result="0" style="text-decoration-color: rgba(0, 0, 0, 0.258824);">Thursday, OCTOBER 3</a><br>John Crerar Library 390 <a href="x-apple-data-detectors://1" dir="ltr" x-apple-data-detectors="true" x-apple-data-detectors-type="calendar-event" x-apple-data-detectors-result="1" style="text-decoration-color: rgba(0, 0, 0, 0.258824);">@3:30pm</a><br><br>Yevgeniy Dodis (NYU)<br>New York University<br><br>Title: Seedless Fruit is the Sweetest: Random Number Generation, Revisited<br><br>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.<br><br>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.<br>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.<br><br>Joint work with Sandro Coretti, Harish Karthikeyan, and Stefano Tessaro.<br></span><div dir="ltr"></div></body></html>