Prof. Dean Doron

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 ∈ 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, nonmalleable 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.