International Association
for Cryptologic Research

Motivated by the problem of how to communicate over a public channel with an active adversary, Dodis and Wichs [DW09] introduced the notion of a non-malleable extractor, as a much stronger version of a strong extractor. A non-malleable extractor $\\textsf{nmExt}$ takes two inputs, a weakly-random $W$ and a uniformly random seed $S$, and outputs a string which is nearly uniform, given $S$ as well as $\\textsf{nmExt}(W, \\mathcal{A}(S))$, for an arbitrary function $\\mathcal{A}$ with $\\mathcal{A}(S) \\neq S$.

Cohen, Raz and Segev in CCC\'12 presented an explicit construction of a non-malleable extractor with short seeds. For any integers $n$ and $d$ such that $2.01 \\cdot \\log n \\leq d \\leq n$, they proposed an explicit construction of a non-malleable extractor $\\textsf{nmExt}: \\{0, 1\\}^n \\times \\{0, 1\\}^d \\rightarrow \\{0, 1\\}^m$ with error exponentially small in $m$. However, their result suffers from some drawbacks: First, the non-malleable extractor is constructed based on Raz\'s etractor in SOTC\'05, while the error estimation in that construction is too rough. Second, though they aimed to shorten the length of the seed, the lower bound of the seed length is not optimal. Moreover, their construction requires the min-entropy rate to be greater than $\\frac{1}{2}$.

In this paper, we improve the error estimation of Raz\'s extractor, which plays an extremely important role in the constraints of the non-malleable extractor parameters including the seed length. Then we present an improved explicit construction of non-malleable extractors with shorter seed length by using biased variable sequence for linear tests. More precisely, we construct an explicit $(1016, \\frac{1}{2})-1-$non-malleable extractor $\\textsf{nmExt}: \\{0, 1\\}^{2^{10}} \\times \\{0, 1\\}^d \\rightarrow \\{0, 1\\}$ with seed length 19, while it should be no less than $\\frac{46}{63} + 66$ according to Cohen et al. in CCC\'12. Therefore, it beats the condition ``$2.01 \\cdot \\log n \\leq d \\leq n$\", since $d$ is just $1.9 \\cdot \\log n$ in our construction. We also give a general explicit construction of non-malleable extractors and analyze the simplification of the constraints on the parameters.

Furthermore, we show an explicit construction of non-malleable extractors for the min-entropy $k = ( \\frac{1}{2} - \\delta)n$ for some constant $ \\delta > 0$, while the min-entropy should be greater than $ \\frac{1}{2} n$ by Cohen et al. in CCC\'12. We also propose a general construction of non-malleable extractors with min-entropy $k = ( \\frac{1}{2} - \\delta)n$ from any non-malleable extractor with min-entropy $k > \\frac{1}{2} n$ by employing a special encoding technique and the property of statical distance. Compared with Li\'s construction in FOCS\'12 by using inner product function, our construction is more general. Finally, we give their application to privacy amplification.