An Entropy Lower Bound for Non-Malleable Extractors

Abstract

A $(k,\epsilon )$-non-malleable extractor is a function $\mathsf{nmExt}:\{0,1{\}}^n\times \{0,1{\}}^d\to \{0,1\}$ that takes two inputs, a weak source $X\sim \{0,1{\}}^n$ of min-entropy $k$ and an independent uniform seed $s\in \{0,1{\}}^d$, and outputs a bit $\mathsf{nmExt}(X,s)$ that is $\epsilon$-close to uniform, even given the seed $s$ and the value $\mathsf{nmExt}(X,s^{\prime })$ for an adversarially chosen seed $s^{\prime }\ne s$. Dodis and Wichs~(STOC 2009) showed the existence of $(k,\epsilon )$-non-malleable extractors with seed length $d=\log (n-k-1)+2\log (1/\epsilon )+6$ that support sources of entropy $k>\log (d)+2\log (1/\epsilon )+8$. We show that the foregoing bound is essentially tight, by proving that any $(k,\epsilon )$-non-malleable extractor must satisfy the entropy bound $k>\log (d)+2\log (1/\epsilon )-\log \log (1/\epsilon )-C$ for an absolute constant $C$. In particular, this implies that non-malleable extractors require min-entropy at least $\Omega (\log \log (n))$. This is in stark contrast to the existence of strong seeded extractors that support sources of entropy $k=O(\log (1/\epsilon ))$. Our techniques strongly rely on coding theory. In particular, we reveal an inherent connection between non-malleable extractors and error correcting codes, by proving a new lemma which shows that any $(k,\epsilon )$-non-malleable extractor with seed length $d$ induces a code $C\subseteq \{0,1{\}}^{2^k}$ with relative distance $0.5-2\epsilon$ and rate $\frac{d-1}{2^k}$.

14 pages, 1 figure