Motivated by the classical problem of privacy amplification, Dodis and
Wichs (STOC '09) introduced the notion of a non-malleable extractor,
significantly strengthening the notion of a strong extractor.
A non-malleable extractor is a function $
mExt : \{0,1\}^n \times
\{0,1\}^d \rightarrow \{0,1\}^m$ that takes two inputs: a weak source $W$
and a uniform (independent) seed $S$, and outputs a string $
mExt(W,S)$
that is nearly uniform given the seed $S$ as well as the value $
mExt(W,
S')$ for any seed $S'
eq S$ that may be determined as an arbitrary
function of $S$.
The first explicit construction of a non-malleable extractor was recently
provided by Li, Wooley and Zuckerman (arXiv:1102.5415 '11). Their
extractor works for any weak source with min-entropy rate $1/2 + \delta$,
where $\delta > 0$ is an arbitrary constant, and outputs up to a linear
number of bits, but suffers from two drawbacks. First, the length of its
seed is linear in the length of the weak source (which leads to privacy
amplification protocols with high communication complexity). Second, the
construction is conditional: when outputting more than a logarithmic
number of bits (as required for privacy amplification protocols) its
efficiency relies on a longstanding conjecture on the distribution of
prime numbers.
In this work we present an unconditional construction of a non-malleable
extractor with short seeds. For any integers $n$ and $d$ such that $2.01
\cdot \log{n} \le d \le n$, we present an explicit construction of a
non-malleable extractor $
mExt \colon \{0,1\}^n \times \{0,1\}^d
\rightarrow \{0,1\}^m$, with $m=\Omega(d)$, and error exponentially small
in $m$. The extractor works for any weak source with min-entropy rate $1/2
+ \delta$, where $\delta > 0$ is an arbitrary constant.
Moreover, our extractor in fact satisfies an even more general notion of
non-malleability: its output $
mExt(W,S)$ is nearly uniform given the
seed $S$ as well as the values $
mExt(W, S_1), \ldots,
mExt(W, S_t)$
for several seeds $S_1, \ldots, S_t$ that may be determined as an
arbitrary function of $S$, as long as $S
otin \{S_1, \ldots, S_t\}$.
By instantiating the framework of Dodis and Wichs with our non-malleable
extractor, we obtain the first $2$-round privacy amplification protocol
for min-entropy rate $1/2 + \delta$ with asymptotically optimal entropy
loss and poly-logarithmic communication complexity. This improves the
previously known $2$-round privacy amplification protocols: the protocol
of Dodis and Wichs whose entropy loss is not asymptotically optimal, and
the protocol of Li, Wooley and Zuckerman whose communication complexity is
linear.
Joint work with Ran Raz and Gil Segev.
Link: http://eccc.hpi-web.de/report/2011/096/