Theory of Computing
-------------------
Title     : Seed-Protecting Extractors
Authors   : Gil Cohen, Dean Doron, and Shahar Samocha
Volume    : 21
Number    : 8
Pages     : 1-38
URL       : https://theoryofcomputing.org/articles/v021a008

Abstract
--------

We introduce a new type of seeded extractors we dub _seed-protecting_ 
extractors. Informally, a seeded extractor is seed protecting against
a class C of functions, mappings seeds to seeds, if the seed Y remains
close to uniform even after observing the output Ext(X, A(Y)) for every
choice of A \in C (or, more generally, observing the outputs corresponding
to several adversaries from C).

The results of this paper are structural. We establish what we believe
to be surprising relations, in fact, _equivalences_ between seed-
protecting extractors and each of the well-studied strengthenings of
seeded extractors: strong extractors, non-malleable extractors (albeit
only against permutations), and two-source extractors, where each case
is classified by a suitable class C.

Our work motivates the study of non-malleable extractors against
permutations and puts forth a novel approach for their construction.
Indeed, the existing machinery developed for constructing non-
malleable extractors focuses on the _output_ and so it is aimed
towards breaking correlations. Instead, our work suggests developing
techniques for protecting the _seed_.