Author name cluster

Jesse Goodman

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

6 papers

1 author row

STOC Conference 2025 Conference Paper

Leakage-Resilient Extractors against Number-on-Forehead Protocols

Eshan Chattopadhyay
Jesse Goodman

Given a sequence of N independent sources X 1 , X 2 ,…, X N ∼{0,1} n , how many of them must be good (i.e., contain some min-entropy) in order to extract a uniformly random string? This question was first raised by Chattopadhyay, Goodman, Goyal and Li (STOC ’20), motivated by applications in cryptography, distributed computing, and the unreliable nature of real-world sources of randomness. In their paper, they showed how to construct explicit low-error extractors for just K ≥ N 1/2 good sources of polylogarithmic min-entropy. In a follow-up, Chattopadhyay and Goodman improved the number of good sources required to just K ≥ N 0.01 (FOCS ’21). In this paper, we finally achieve K =3. Our key ingredient is a near-optimal explicit construction of a 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 Li’s low-error three-source extractor (FOCS ’15), and resolves an open question put forth 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.

Details

FOCS Conference 2024 Conference Paper

Improved Condensers for Chor-Goldreich Sources

Jesse Goodman
Xin Li 0006
David Zuckerman

One of the earliest models of weak randomness is the Chor-Goldreich (CG) source. A $(t, n, k)\text{-}$ CG source is a sequence of random variables X $=(\mathrm{x}_{1}, \ldots, \mathrm{x}_{t})\sim(\{0, 1\}^{n})^{t}$, where each $\mathrm{X}_{i}$ has min-entropy $k$ conditioned on any fixing of $\mathrm{x}_{1}, \ldots, \mathrm{x}_{i-1}$. Chor and Goldreich proved that there is no deterministic way to extract randomness from such a source. Nevertheless, Doron, Moshkovitz, Oh, and Zuckerman showed that there is a deterministic way to condense a CG source into a string with small entropy gap. They gave applications of such a condenser to simulating randomized algorithms with small error and to certain cryptographic tasks. They studied the case where the block length $n$ and entropy rate $k/n$ are both constant. We study the much more general setting where the block length can be arbitrarily large, and the entropy rate can be arbitrarily small. We construct the first explicit condenser for CG sources in this setting, and it can be instantiated in a number of different ways. When the entropy rate of the CG source is constant, our condenser requires just a constant number of blocks $t$ to produce an output with entropy rate 0. 9, say. In the low entropy regime, using $t= \text{poly} (n)$ blocks, our condenser can achieve output entropy rate 0. 9 even if each block has just 1 bit of min-entropy. Moreover, these condensers have exponentially small error. Finally, we provide strong existential and impossibility results. For our existential result, we show that a random function is a seedless condenser (with surprisingly strong parameters) for any small family of sources. As a corollary, we get new existential results for seeded condensers and condensers for CG sources. For our impossibility result, we show the latter result is nearly tight, by giving a simple proof that the output of any condenser for CG sources must inherit the entropy gap of (one block of) its input.

Details

FOCS Conference 2021 Conference Paper

Affine Extractors for Almost Logarithmic Entropy

Eshan Chattopadhyay
Jesse Goodman
Jyun-Jie Liao

We give an explicit construction of an affine extractor (over $\mathbb{F}_{2}$ ) that works for affine sources on $n$ bits with min-entropy $k\geq\log n\cdot(\log\log n)^{1+o(1)}$. This improves prior work of Li (FOCS'16) that requires min-entropy at least $\text{poly} (\log n)$. Our construction is based on the framework of using correlation breakers and resilient functions, a paradigm that was also used by Li. On a high level, the key sources of our improvement are based on the following new ingredients: (i) A new construction of an affine somewhere random extractor, that we use in a crucial step instead of a linear seeded extractor (for which optimal constructions are not known) that was used by Li. (ii) A near optimal construction of a correlation breaker for linearly correlated sources. The construction of our correlation breaker takes inspiration from an exciting line of recent work that constructs two-source extractors for near logarithmic min-entropy.

Details

FOCS Conference 2021 Conference Paper

Improved Extractors for Small-Space Sources

Eshan Chattopadhyay
Jesse Goodman

We study the problem of extracting random bits from weak sources that are sampled by algorithms with limited memory. This model of small-space sources was introduced by Kamp, Rao, Vadhan and Zuckerman (STOC'06), and falls into a line of research initiated by Trevisan and Vadhan (FOCS'00) on extracting randomness from weak sources that are sampled by computationally bounded algorithms. Our main results are the following. 1) We obtain near-optimal extractors for small-space sources in the polynomial error regime. For space $s$ sources over $n$ bits, our extractors require just $k\geq s. \text{polylog} (n)$ entropy. This is an exponential improvement over the previous best result, which required entropy $k\geq s^{1, 1}\cdot 2^{\log^{0. 51}n}$ (Chattopadhyay and Li, STOC'16). 2) We obtain improved extractors for small-space sources in the negligible error regime. For space $s$ sources over $n$ bits, our extractors require entropy $k > n^{1/2+\delta}\cdot s^{1/2-\delta}$, whereas the previous best result required $k > n^{2/3+\delta}\cdot s^{1/3-\delta}$ (Chattopadhyay, Goodman, Goyal and Li, STOC'20). To obtain our first result, the key ingredient is a new reduction from small-space sources to affine sources, allowing us to simply apply a good affine extractor. To obtain our second result, we must develop some new machinery, since we do not have low-error affine extractors that work for low entropy. Our main tool is a significantly improved extractor for adversarial sources, which is built via a simple framework that makes novel use of a certain kind of leakage-resilient extractors (known as cylinder intersection extractors), by combining them with a general type of extremal designs. Our key ingredient is the first derandomization of these designs, which we obtain using new connections to coding theory and additive combinatorics.

Details

FOCS Conference 2020 Conference Paper

Extractors and Secret Sharing Against Bounded Collusion Protocols

Eshan Chattopadhyay
Jesse Goodman
Vipul Goyal
Ashutosh Kumar 0002
Xin Li 0006
Raghu Meka
David Zuckerman

In a recent work, Kumar, Meka, and Sahai (FOCS 2019) introduced the notion of bounded collusion protocols (BCPs). BCPs are multiparty communication protocols in which N parties, holding n bits each, attempt to compute some joint function of their inputs, f: ({0, 1} n ) N →{0, 1}. In each round, p parties (the collusion bound) work together to write a single bit on a public blackboard, and the protocol continues until every party knows the value of f. BCPs are a natural generalization of the well-studied number-in-hand (NIH) and number-on-forehead (NOF) models, which are just endpoints on this rich spectrum of protocols (corresponding to p=1 and p=N-1, respectively). In this work, we investigate BCPs more thoroughly, and answer questions about them in the context of communication complexity, randomness extractors, and secret sharing. 1. First, we provide explicit lower bounds against BCPs. Our lower bounds offer a tradeoff between collusion and complexity, and are of the form n Ω(1) when p=0. 99N parties collude. This bound is independent of the relationship between N, n, whereas all previous bounds became trivial when. 2. Second, we provide explicit leakage-resilient extractors against BCPs. Also known as cylinder-intersection extractors, these objects are multi-source extractors of the form Ext: ({0, 1} n ) N →{0, 1}, whose output looks uniform even conditioned on the bits produced (“leaked”) by a BCP executed over the inputs of the extractor. Our extractors work for sources with min-entropy k ≥ polylog(n) against BCPs with collusion p ≤ N-2. Previously, all such extractors required min-entropy k ≥ 0. 99n even when p ≤ O(1). 3. Third, we provide efficient leakage-resilient secret sharing schemes against BCPs. These cryptographic primitives are standard t-out-of- N secret sharing schemes, equipped with an additional guarantee that the secret remains hidden even if the individuals participate in a BCP using their shares. Our schemes can handle collusion up to p ≤ O(t/logt), whereas the previous best scheme required p ≤ O(logN). Along the way, we also construct objects that are more general than those listed above (i. e. , compilers), objects that are more specialized (and stronger) than those listed above, and resolve open questions posed by Goyal and Kumar (STOC 2018) and Kumar, Meka, and Sahai (FOCS 2019).

Details

STOC Conference 2020 Conference Paper

Extractors for adversarial sources via extremal hypergraphs

Eshan Chattopadhyay
Jesse Goodman
Vipul Goyal
Xin Li 0006

Randomness extraction is a fundamental problem that has been studied for over three decades. A well-studied setting assumes that one has access to multiple independent weak random sources, each with some entropy. However, this assumption is often unrealistic in practice. In real life, natural sources of randomness can produce samples with no entropy at all or with unwanted dependence. Motivated by this and applications from cryptography, we initiate a systematic study of randomness extraction for the class of adversarial sources defined as follows. A weak source X of the form X 1 , …, X N , where each X i is on n bits, is an ( N , K , n , k )-source of locality d if the following hold: (1) Somewhere good sources: at least K of the X i ’s are independent, and each contains min-entropy at least k . We call these X i ’s good sources, and their locations are unknown. (2) Bounded dependence: each remaining (bad) source can depend arbitrarily on at most d good sources. We focus on constructing extractors with negligible error, in the regime where most of the entropy is contained within a few sources instead of across many (i.e., k is at least polynomial in K ). In this setting, even for the case of 0-locality, very little is known prior to our work. For d =1, essentially no previous results are known. We present various new extractors for adversarial sources in a wide range of parameters, and some of our constructions work for locality d = K Ω(1) . As an application, we also give improved extractors for small-space sources. The class of adversarial sources generalizes several previously studied classes of sources, and our explicit extractor constructions exploit tools from recent advances in extractor machinery, such as two-source non-malleable extractors and low-error condensers. Thus, our constructions can be viewed as a new application of non-malleable extractors. In addition, our constructions combine the tools from extractor theory in a novel way through various sorts of explicit extremal hypergraphs. These connections leverage recent progress in combinatorics, such as improved bounds on cap sets and explicit constructions of Ramsey graphs, and may be of independent interest.

Details