A (k,\eps)-non-malleable extractor is a function nmExt : {0,1}^n x {0,1}^d -> {0,1} that takes two inputs, a weak source X~{0,1}^n of min-entropy k and an independent uniform seed s in {0,1}^d, and outputs a bit nmExt(X, s) that is \eps-close to uniform, even given the seed s and the value nmExt(X, s') for an adversarially chosen seed s' \neq s. Dodis and Wichs~(STOC 2009) showed the existence of (k, \eps)-non-malleable extractors with seed length d = \log(n-k-1) + 2\log(1/\eps) + 6 that support sources of entropy k > \log(d) + 2 \log(1/\eps) + 8.

We show that the foregoing bound is essentially tight by proving that any (k,\eps)-non-malleable extractor must satisfy the entropy bound k > \log(d) + 2 \log(1/\eps) - \log\log(1/\eps) - 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/\eps)).

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,\eps)-non-malleable extractor with seed length d induces a code C \seq {0,1}^{2^k} with relative distance 0.5 - 2\eps and rate (d-1)/(2^k).