Welcome to the resource topic for 2012/188
Title:
Non-Malleable Extractors, Two-Source Extractors and Privacy Amplification
Authors: 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}.
ePrint: https://eprint.iacr.org/2012/188
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .