Paper 2014/156

Non-Malleable Extractors with Shorter Seeds and Privacy Amplification

Yanqing Yao, Zhoujun Li

Abstract

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. A non-malleable extractor $\textsf{nmExt}: \{0, 1\}^n \times \{0, 1\}^d \rightarrow \{0, 1\}^m$ 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$. 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, where the seed length is shorter than that by Cohen, Raz and Segev [CCC12]. 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$" in CCC'12, 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. Finally, we give their application to privacy amplification.