Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR11-161 | 4th December 2011 07:18

Design Extractors, Non-Malleable Condensers and Privacy Amplification


Authors: Xin Li
Publication: 4th December 2011 14:17
Downloads: 2164


We introduce a new combinatorial object, called a \emph{design extractor}, that has both the properties of a design and an extractor. We give efficient constructions of such objects and show that they can be used in several applications.

\item {Improving the output length of known non-malleable extractors.} Non-malleable extractors were introduced in \cite{DW09} to study the problem of privacy amplification with an active adversary. Currently, only two explicit constructions are known \cite{DLWZ11, CRS11}. Both constructions work for $n$ bit sources with min-entropy $k > n/2$. However, in both constructions the output length is smaller than the seed length, while the probabilistic method shows that to achieve error $\e$, one can use $O(\log n+\log (1/\e))$ bits to extract up to $k/2$ output bits. In this paper, we use our design extractor to give an explicit non-malleable extractor for min-entropy $k > n/2$, that has seed length $O(\log n+\log (1/\e))$ and output length $\Omega(k)$.

\item {Non-malleable condensers.} We introduce and define the notion of a \emph{non-malleable condenser}. A non-malleable condenser is a generalization and relaxation of a non-malleable extractor. We show that similar as extractors and condensers, non-malleable condensers can be used to construct non-malleable extractors. We then show that our design extractor already gives a non-malleable condenser for min-entropy $k > n/2$, with error $\e$ and seed length $O(\log (1/\e))$.

\item {A new optimal protocol for privacy amplification.} More surprisingly, we show that non-malleable condensers themselves give optimal privacy amplification protocols with an active adversary. In fact, the non-malleable condensers used in these protocols are much weaker compared to non-malleable extractors, in the sense that the entropy rate of the condenser's output does not need to increase at all. This suggests that one promising next step to achieve better privacy amplification protocols may be to construct non-malleable condensers for smaller min-entropy. As a by-product, we also obtain a new explicit 2-round privacy amplification protocol with optimal entropy loss and optimal communication complexity for min-entropy $k > n/2$, without using non-malleable extractors.

ISSN 1433-8092 | Imprint