Eshan Chattopadhyay

Eshan Chattopadhyay, Mohit Gurumukhani, Noam Ringach et al.

Random selection, leader election, and collective coin flipping are fundamental tasks in fault-tolerant distributed computing. We study these problems in the full-information model where despite decades of study, key gaps remain in our understanding of the trade-offs between round complexity, communication per player in each round, and adversarial resilience. We make progress by proving improved bounds for these problems. We first show that any $k$-round coin flipping protocol over $\ell$ players, each player sending one bit per round, can be biased by $O(\ell/\log^{(k)}(\ell))$ bad players. We obtain a similar lower bound for leader election. This strengthens prior best bounds [RSZ, SICOMP 2002] of $O(\ell/\log^{(2k-1)}(\ell))$ for coin flipping protocols and $O(\ell/\log^{(2k+1)}(\ell))$ for leader election protocols. Our result implies that any (1-bit per player) protocol tolerating linear fraction of bad players requires at least $\log^* \ell$ rounds, showing existing protocols [RZ, JCSS 2001; F, FOCS 1999] are near-optimal. We next initiate the study of one-round, (1-bit per player) random selection. For all $m\ge (\log(\ell))^2$, we obtain an optimal protocol (a first in the full information model for any task): We construct a protocol resilient to $O(\ell / m)$ bad players that outputs $m$ uniform random bits. And, we show that any protocol that outputs $m$ uniform random bits can be corrupted using $O(\ell / m)$ bad players. This also implies a one-round leader election protocol resilient to $\ell / (\log \ell)^2$ bad players, improving the prior best protocol [RZ, JCSS 2001] which was resilient to $\ell / (\log \ell)^3$ bad players. Our resilience matches that of the best one-round coin flipping protocol by Ajtai & Linial. To obtain our lower bound, we introduce multi-output influence, an extension of influence of boolean functions to the multi-output setting.

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\cdot$polylog$(n)$ entropy. This is an exponential improvement over the previous best result, which required $k\geq s^{1.1}\cdot2^{\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\geq n^{1/2+δ}\cdot s^{1/2-δ}$, whereas the previous best result required $k\geq n^{2/3+δ}\cdot s^{1/3-δ}$ (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.

Eshan Chattopadhyay, Xin Li

Non-malleable codes were introduced by Dziembowski, Pietrzak, and Wichs (JACM 2018) as a generalization of standard error correcting codes to handle severe forms of tampering on codewords. This notion has attracted a lot of recent research, resulting in various explicit constructions, which have found applications in tamper-resilient cryptography and connections to other pseudorandom objects in theoretical computer science. We continue the line of investigation on explicit constructions of non-malleable codes in the information theoretic setting, and give explicit constructions for several new classes of tampering functions. (1) Interleaved split-state tampering: Here the codeword is partitioned in an unknown way by an adversary, and then tampered with by a split-state tampering function. (2) Linear function composed with split-state tampering: In this model, the codeword is first tampered with by a split-state adversary, and then the whole tampered codeword is further tampered with by a linear function. In fact our results are stronger, and we can handle linear function composed with interleaved split-state tampering. (3) Bounded communication split-state tampering: In this model, the two split-state tampering adversaries are allowed to participate in a communication protocol with a bounded communication budget. Our results are the first explicit constructions of non-malleable codes in any of these tampering models. We derive all these results from explicit constructions of seedless non-malleable extractors, which we believe are of independent interest. Using our techniques, we also give an improved seedless extractor for an unknown interleaving of two independent sources.

Eshan Chattopadhyay, Xin Li

We make progress in the following three problems: 1. Constructing optimal seeded non-malleable extractors; 2. Constructing optimal privacy amplification protocols with an active adversary, for any security parameter; 3. Constructing extractors for independent weak random sources, when the min-entropy is extremely small (i.e., near logarithmic). For the first two problems, the best known non-malleable extractors by Chattopadhyay, Goyal and Li [CGL16], and by Cohen [Coh16a,Coh16b] all require seed length and min-entropy at least $\log^2 (1/ε)$, where $ε$ is the error of the extractor. As a result, the best known explicit privacy amplification protocols with an active adversary, which achieve 2 rounds of communication and optimal entropy loss in [Li15c,CGL16], can only handle security parameter up to $s=Ω(\sqrt{k})$, where $k$ is the min-entropy of the shared secret weak random source. For larger $s$ the best known protocol with optimal entropy loss in [Li15c] requires $O(s/\sqrt{k})$ rounds of communication. In this paper we give an explicit non-malleable extractor that only requires seed length and min-entropy $\log^{1+o(1)} (n/ε)$, which also yields a 2-round privacy amplification protocol with optimal entropy loss for security parameter up to $s=k^{1-α}$ for any constant $α>0$. For the third problem, previously the best known extractor which supports the smallest min-entropy due to Li [Li13a], requires min-entropy $\log^{2+δ} n$ and uses $O(1/δ)$ sources, for any constant $δ>0$. A very recent result by Cohen and Schulman [CS16] improves this, and constructed explicit extractors that use $O(1/δ)$ sources for min-entropy $\log^{1+δ} n$, any constant $δ>0$. In this paper we further improve their result, and give an explicit extractor that uses $O(1)$ (an absolute constant) sources for min-entropy $\log^{1+o(1)} n$.

Eshan Chattopadhyay, Vipul Goyal, Xin Li

Randomness extractors and error correcting codes are fundamental objects in computer science. Recently, there have been several natural generalizations of these objects, in the context and study of tamper resilient cryptography. These are seeded non-malleable extractors, introduced in [DW09]; seedless non-malleable extractors, introduced in [CG14b]; and non-malleable codes, introduced in [DPW10]. However, explicit constructions of non-malleable extractors appear to be hard, and the known constructions are far behind their non-tampered counterparts. In this paper we make progress towards solving the above problems. Our contributions are as follows. (1) We construct an explicit seeded non-malleable extractor for min-entropy $k \geq \log^2 n$. This dramatically improves all previous results and gives a simpler 2-round privacy amplification protocol with optimal entropy loss, matching the best known result in [Li15b]. (2) We construct the first explicit non-malleable two-source extractor for min-entropy $k \geq n-n^{Ω(1)}$, with output size $n^{Ω(1)}$ and error $2^{-n^{Ω(1)}}$. (3) We initiate the study of two natural generalizations of seedless non-malleable extractors and non-malleable codes, where the sources or the codeword may be tampered many times. We construct the first explicit non-malleable two-source extractor with tampering degree $t$ up to $n^{Ω(1)}$, which works for min-entropy $k \geq n-n^{Ω(1)}$, with output size $n^{Ω(1)}$ and error $2^{-n^{Ω(1)}}$. We show that we can efficiently sample uniformly from any pre-image. By the connection in [CG14b], we also obtain the first explicit non-malleable codes with tampering degree $t$ up to $n^{Ω(1)}$, relative rate $n^{Ω(1)}/n$, and error $2^{-n^{Ω(1)}}$.