2018/01/10 by Tom Gur, Gur, Tom, Igor Shinkar +1
Computer Science · #Computational Complexity (cs.CC) #FOS: Computer and information sciences #cs.CC
paper · pdf · doi:10.48550/arxiv.1801.03200
14 pages, 1 figure
arxiv created 2018/01/10 · arxiv updated 2018/01/11
A (k,ε)-non-malleable extractor is a function \sf nmExt : \0,1\n × \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 ∈ \0,1\d, and outputs a bit \sf nmExt(X, s) that is ε-close to uniform, even given the seed s and the value \sf nmExt(X, s') for an adversarially chosen seed s' ≠ s. Dodis and Wichs~(STOC 2009) showed the existence of (k, ε)-non-malleable extractors with seed length d = log(n-k-1) + 2log(1/ε) + 6 that support sources of entropy k > log(d) + 2 log(1/ε) + 8. We show that the foregoing bound is essentially tight, by proving that any (k,ε)-non-malleable extractor must satisfy the entropy bound k > log(d) + 2 log(1/ε) - loglog(1/ε) - C for an absolute constant C. In particular, this implies that non-malleable extractors require min-entropy at least Ω(loglog(n)). This is in stark contrast to the existence of strong seeded extractors that support sources of entropy k = O(log(1/ε)). 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,ε)-non-malleable extractor with seed length d induces a code C ⊆ \0,1\2k with relative distance 0.5 - 2ε and rate (d-1)/(2k).