News & Events

Theory of Computation Seminars

Seedless Fruit is the Sweetest: Random Number Generation, Revisited

Yevgeniy Dodis, Professor of Computer Science, New York University

Nov 25, 2019

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.

Speaker Bio

Yevgeniy Dodis is a Professor of computer science at New York University. Dr. Dodis received his summa cum laude Bachelors degree in Mathematics and Computer Science from New York University in 1996, and his PhD degree in Computer Science from MIT in 2000. Dr. Dodis was a post-doc at IBM T.J.Watson Research center in 2000, and joined New York University as an Assistant Professor in 2001. He was promoted to Associate Professor in 2007 and Full Professor in 2012.

Dr. Dodis' research is primarily in cryptography and network security. In particular, he worked in a variety of areas including random number generation, leakage-resilient cryptography, cryptography under weak randomness, cryptography with biometrics and other noisy data, hash function and block cipher design, protocol composition and information-theoretic cryptography. Dr. Dodis has more than 130 scientific publications at various conferences, journals and other venues, was the Program co-Chair for the 2015 Theory of Cryptography Conference and the editor of Journal of Cryptology, has been on program committees of many international conferences (including FOCS, STOC, CRYPTO and Eurocrypt), and gave numerous invited lectures and courses at various venues.

Dr. Dodis is the recipient of 2019 IACR Test-of-Time Award for his work on Fuzzy Extractors, National Science Foundation CAREER Award, Faculty Awards from Facebook, Google, IBM and VMware, and Best Paper Award at 2005 Public Key Cryptography Conference. As an undergraduate student, he was also a winner of the US-Canada Putnam Mathematical Competition in 1995.


Carol Harlow