Non-Malleable Extractors - New Tools and Improved Constructions
by Gil Cohen
This may well be the best place to learn about
the recent breakthrough
in the study of two-source randomness extractors,
which are based on the recent construction of non-malleable extractors.
I should admit that I failed to see the potential of these strong constructs,
viewing them as related to a specific cryptographic application (from
which they have emerged). But as became evident recently, these constructs
play an important role in the construction of more ``mainstream'' objects.
The current work abstracts and decouples the various ideas that underline
the construction of non-malleable extractors, making this highly complex
material significantly more accessible to non-experts (i.e., researchers
who have not studied non-malleable extractors so far).
The original abstract
A non-malleable extractor is a seeded extractor with a very strong
guarantee - the output of a non-malleable extractor obtained using a
typical seed is close to uniform even conditioned on the output obtained
using any other seed. The first contribution of this paper consists of two
new and improved constructions of non-malleable extractors:
We further devise several tools for enhancing a given non-malleable
extractor in a black-box manner. One such tool is an algorithm that reduces
the entropy requirement of a non-malleable extractor at the expense of a
slightly longer seed. A second algorithm increases the output length of a
non-malleable extractor from constant to linear in the entropy of the
source. We also devise an algorithm that transforms a non-malleable
extractor to the so-called t-non-malleable extractor for any desired t.
Besides being useful building blocks for our constructions, we consider
these modular tools to be of independent interest.
- We construct a non-malleable extractor with seed-length O(logn loglogn)
that works for entropy Omega(logn). This improves upon a recent exciting
construction by Chattopadhyay, Goyal, and Li (ECCC'15) that has seed length
O(log^2 n) and requires entropy (log^2 n).
- Secondly, we construct a non-malleable extractor with optimal seed length
O(logn) for entropy n/polylogn . Prior to this construction, non-malleable
extractors with a logarithmic seed length, due to Li (FOCS'12), required
entropy 049n. Even non-malleable condensers with seed length O(logn), by Li
(STOC'12), could only support linear entropy.
See ECCC TR15-183.
list of Oded's choices.