Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR20-161 | 5th November 2020 21:59

Seed Protecting Extractors


Authors: Gil Cohen, Dean Doron, Shahar Samocha
Publication: 5th November 2020 22:06
Downloads: 675


We introduce a new type of seeded extractors we dub seed protecting extractors. Informally, a seeded extractor is seed protecting against a class of functions $C$, mappings seeds to seeds, if the seed $Y$ remains close to uniform even after observing the output $\mathrm{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 (against permutations), and two-source extractors, where each case is classified by a suitable class $C$. Our work put forth a novel approach for constructing nonmalleable extractors against permutations. 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.

ISSN 1433-8092 | Imprint