__
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: 1335

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}$.