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: 417
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