Randomness extractors for a few hidden sources

Title: Randomness extractors for a few hidden sources

Abstract: Given a sequence of N independent sources of randomness X_1, …, X_N, how many of them must be *good* (i.e., contain some entropy) in order to extract a uniformly random string? This question was first raised at STOC’20, motivated by applications in cryptography, and by the unreliable nature of real-world randomness. There, it was shown how to extract uniform bits with very low error, even when just K = N^{0.5} of the sources are good. In a follow-up work at FOCS’21, the number of good sources required was significantly improved to K = N^{0.01}.

In this talk, I will discuss our new work that achieves K = 3.

Our key ingredient is a near-optimal explicit construction of a powerful new pseudorandom primitive, called a “leakage-resilient extractor (LRE) against number-on-forehead (NOF) protocols.” Our LRE can be viewed as a significantly more robust version of classical independent source extractors, and resolves an open question by Kumar, Meka, and Sahai (FOCS’19) and Chattopadhyay, Goodman, Goyal, Kumar, Li, Meka, and Zuckerman (FOCS’20). Our LRE construction is based on a simple new connection we discover between multiparty communication complexity and “non-malleable” extractors, which shows that such extractors exhibit strong average-case lower bounds against NOF protocols.

Based on joint work with Eshan Chattopadhyay (STOC’25, to appear).

Bio: Jesse Goodman is a Postdoctoral Fellow at UT Austin, where he is hosted by David Zuckerman. Previously, he received his PhD from Cornell University, advised by Eshan Chattopadhyay, and his BSE from Princeton University. His primary research interests lie in pseudorandomness, complexity theory, and combinatorics.