Paper 2019/1450
Extractors for Adversarial Sources via Extremal Hypergraphs
Eshan Chattopadhyay, Jesse Goodman, Vipul Goyal, and Xin Li
Abstract
Randomness extraction is a fundamental problem that has been studied for over three decades. A wellstudied 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 $\mathbf{X}$ of the form $\mathbf{X}_1,...,\mathbf{X}_N$, where each $\mathbf{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 $\mathbf{X}_i$'s are independent, and each contains minentropy at least $k$. We call these $\mathbf{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 \geq 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^{\Omega(1)}$. As an application, we also give improved extractors for smallspace 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 twosource nonmalleable extractors and lowerror condensers. Thus, our constructions can be viewed as a new application of nonmalleable 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.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Preprint. MINOR revision.
 Keywords
 extractorsnonmalleable extractorsextremal hypergraphsRamsey graphscap sets
 Contact author(s)

eshanc @ cornell edu
jpmgoodman @ cs cornell edu
vipul @ cmu edu
lixints @ cs jhu edu  History
 20191216: received
 Short URL
 https://ia.cr/2019/1450
 License

CC BY
BibTeX
@misc{cryptoeprint:2019/1450, author = {Eshan Chattopadhyay and Jesse Goodman and Vipul Goyal and Xin Li}, title = {Extractors for Adversarial Sources via Extremal Hypergraphs}, howpublished = {Cryptology {ePrint} Archive, Paper 2019/1450}, year = {2019}, url = {https://eprint.iacr.org/2019/1450} }