Non-Malleable Extractors - New Tools and Improved Constructions

by Gil Cohen

Oded's comments

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.

See ECCC TR15-183.

Back to list of Oded's choices.