[Colloquium] Theory speaker Yevgeniy Dodis

[Donna Brooms]

REMINDER: 

Department of Mathematics & Computer Science
Combinatorics & Theory Seminar

NON-STANDARD DAY
Thursday, October 3, 2019
Crerar 390 @ 3:30 pm

Yevgeniy Dodis
NYU
http://cs.nyu.edu/~dodis <http://cs.nyu.edu/~dodis>

Title: “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 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.

Host: Prof. David Cash



Donna Brooms-Blue




Department Secretary
Computer Science Department
John Crerar Library Building
5730 So. Ellis Ave.
Chicago, IL. 60637
(773) 702-6614 - Office
(773) 702-8487 - Fax
donna at cs.uchicago.edu

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20191003/dd0364a5/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image001.gif
Type: image/gif
Size: 2340 bytes
Desc: not available
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20191003/dd0364a5/attachment-0001.gif>