Dodis and Wichs \cite{DW09} 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 $\mathsf{nmExt}$ has the property that $\nm(x,y)$ appears uniform even given $y$ as well as $\mathsf{nmExt}(x,\adv(y))$, for an arbitrary function $\calA$ with $\calA(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 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}.
This version adds a lot of new results, including a strong connection between non-malleable extractors and two-source extractors, and the first optimal privacy amplification protocol for arbitrarily linear min-entropy
Dodis and Wichs \cite{DW09} 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 explicit constructions of non-malleable extractors \cite{DLWZ11, CRS11}. Both constructions only work for $(n, k)$-sources with $k>n/2$ and thus they also only achieve optimal privacy amplification protocols for $k>n/2$. In this paper, we give the first construction of non-malleable extractors for
entropy rate below 1/2. Specifically, we give two unconditional constructions for min-entropy $k=(1/2-\delta)n$ for some constant $\delta>0$ and a conditional construction that can potentially achieve $k=\alpha n$ for any constant $\alpha>0$. Using our non-malleable extractor, we also obtain the first optimal privacy amplification protocol for min-entropy $k=(1/2-\delta)n$, with an active adversary.
Our constructions mainly use the bilinear property of the inner product function, and involve appropriate encodings of the seed $y$ as well as ideas from additive combinatorics.
