Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR16-030 | 7th March 2016 21:56

Non-Malleable Extractors with Logarithmic Seeds

RSS-Feed




TR16-030
Authors: Gil Cohen
Publication: 7th March 2016 21:59
Downloads: 1442
Keywords: 


Abstract:

We construct non-malleable extractors with seed length d = O(\log{n}+\log^{3}(1/\epsilon)) for n-bit sources with min-entropy k = \Omega(d), where \epsilon is the error guarantee. In particular, the seed length is logarithmic in n for \epsilon> 2^{-(\log{n})^{1/3}}. This improves upon existing constructions that either require super-logarithmic seed length even for constant error guarantee, or otherwise only support min-entropy n/\log^{O(1)}{n}.



ISSN 1433-8092 | Imprint