Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR16-030 | 7th March 2016 21:56

#### Non-Malleable Extractors with Logarithmic Seeds

TR16-030
Authors: Gil Cohen
Publication: 7th March 2016 21:59
Downloads: 671
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