ECCC-Report TR18-008https://eccc.weizmann.ac.il/report/2018/008Comments and Revisions published for TR18-008en-usThu, 11 Jan 2018 17:25:59 +0200
Paper TR18-008
| An Entropy Lower Bound for Non-Malleable Extractors |
Tom Gur,
Igor Shinkar
https://eccc.weizmann.ac.il/report/2018/008A (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).Thu, 11 Jan 2018 17:25:59 +0200https://eccc.weizmann.ac.il/report/2018/008