Paper 2012/188

Non-Malleable Extractors, Two-Source Extractors and Privacy Amplification

Xin Li

Abstract

Dodis and Wichs introduced the notion of a non-malleable extractor to study the problem of privacy amplification with an active adversary. A non-malleable extractor is a much stronger version of a strong extractor. Given a weakly-random string $x$ and a uniformly random seed $y$ as the inputs, the non-malleable extractor $nmExt$ has the property that $nmExt(x,y)$ appears uniform even given $y$ as well as $nmExt(x,A(y))$, for an arbitrary function $A$ with $A(y) \neq y$. Dodis and Wichs showed that such an object can be used to give optimal privacy amplification protocols with an active adversary. Previously, there are only two known constructions of non-malleable extractors \cite{DLWZ11, CRS11}. Both constructions only work for $(n, k)$-sources with $k>n/2$. Interestingly, both constructions are also two-source extractors. In this paper, we present a strong connection between non-malleable extractors and two-source extractors. The first part of the connection shows that non-malleable extractors can be used to construct two-source extractors. If the non-malleable extractor works for small min-entropy and has a short seed length with respect to the error, then the resulted two-source extractor beats the best known construction of two-source extractors. This partially explains why previous constructions of non-malleable extractors only work for sources with entropy rate $>1/2$, and why explicit non-malleable extractors for small min-entropy may be hard to get. The second part of the connection shows that certain two-source extractors can be used to construct non-malleable extractors. Using this connection, we obtain the first construction of non-malleable extractors for $k < n/2$. Specifically, we give an unconditional construction for min-entropy $k=(1/2-\delta)n$ for some constant $\delta>0$, and a conditional (semi-explicit) construction that can potentially achieve $k=\alpha n$ for any constant $\alpha>0$. We also generalize non-malleable extractors to the case where there are more than one adversarial seeds, and show a similar connection between the generalized non-malleable extractors and two-source extractors. Finally, despite the lack of explicit non-malleable extractors for arbitrarily linear entropy, we give the first 2-round privacy amplification protocol with asymptotically optimal entropy loss and communication complexity for $(n, k)$ sources with $k=\alpha n$ for any constant $\alpha>0$. This dramatically improves previous results and answers an open problem in \cite{DLWZ11}.