Revised: December 18, 2022
Published: October 28, 2025
Abstract: [Plain Text Version]
$\newcommand{\ccc}{\mathbf{C}}$ $\newcommand{\ext}{\mathsf{Ext}}$ $\newcommand{\adv}{A}$ We introduce a new type of seeded extractors we dub seed-protecting extractors. Informally, a seeded extractor is seed protecting against a class $\ccc$ of functions, mappings seeds to seeds, if the seed $Y$ remains close to uniform even after observing the output $\ext(X,\adv(Y))$ for every choice of $\adv \in \ccc$ (or, more generally, observing the outputs corresponding to several adversaries from $\ccc$).
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 $\ccc$.
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.
Licensed under a Creative Commons Attribution License (CC-BY)