Seed-Protecting Extractors

doi:10.4086/toc.2025.v021a008

Seed-Protecting Extractors

2025-10-28

0

PRE

AI

DOI：10.4086/toc.2025.v021a008

原文链接

原文求助

摘要

En 中文

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 is an element of 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 is aimed towards breaking correlations. Instead, our work suggests developing techniques for protecting the seed.

Keyword:

pseudorandomness

extractors

Seed-Protecting Extractors

摘要

期刊

机构

引用论文