The Library
An entropy lower bound for non-malleable extractors
Tools
Gur, Tom and Shinkar, Igor (2020) An entropy lower bound for non-malleable extractors. IEEE Transactions on Information Theory, 66 (5). pp. 2904-2911. doi:10.1109/TIT.2019.2946896 ISSN 0018-9448.
|
PDF
WRAP-Entropy-lower-bound-non-malleable-extractors-Gur-2019.pdf - Accepted Version - Requires a PDF viewer. Download (843Kb) | Preview |
Official URL: https://doi.org/10.1109/TIT.2019.2946896
Abstract
A (k, ε)-non-malleable extractor is a function 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 E {0, 1} d , and outputs a bit nmExt(X, s) that is ε-close to uniform, even given the seed s and the value 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) + 2 log(1/ε) + 6 that support sources of min-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 min-entropy bound k > log(d) + 2 log(1/ε) - log log(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 min-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 1/2 - 2ε and rate d-1/2k .
Item Type: | Journal Article | ||||||||
---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics Q Science > QC Physics |
||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||||
Library of Congress Subject Headings (LCSH): | Entropy, Coding theory , Machine theory -- Mathematical models, Combinatorial analysis | ||||||||
Journal or Publication Title: | IEEE Transactions on Information Theory | ||||||||
Publisher: | IEEE | ||||||||
ISSN: | 0018-9448 | ||||||||
Official Date: | May 2020 | ||||||||
Dates: |
|
||||||||
Volume: | 66 | ||||||||
Number: | 5 | ||||||||
Page Range: | pp. 2904-2911 | ||||||||
DOI: | 10.1109/TIT.2019.2946896 | ||||||||
Status: | Peer Reviewed | ||||||||
Publication Status: | Published | ||||||||
Reuse Statement (publisher, data, author rights): | © 2019 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. | ||||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||||
Date of first compliant deposit: | 1 October 2019 | ||||||||
Date of first compliant Open Access: | 1 October 2019 | ||||||||
RIOXX Funder/Project Grant: |
|
||||||||
Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year