Welcome to the resource topic for 2021/1002
Title:
Online Linear Extractors for Independent Sources
Authors: Yevgeniy Dodis, Siyao Guo, Noah Stephens-Davidowitz, Zhiye Xie
Abstract:In this work, we characterize online linear extractors. In other words, given a matrix A \in \mathbb{F}_2^{n \times n}, we study the convergence of the iterated process \mathbf{S} \leftarrow A\mathbf{S} \oplus \mathbf{X} , where \mathbf{X} \sim D is repeatedly sampled independently from some fixed (but unknown) distribution D with (min)-entropy at least k. Here, we think of \mathbf{S} \in \{0,1\}^n as the state of an online extractor, and \mathbf{X} \in \{0,1\}^n as its input. As our main result, we show that the state \mathbf{S} converges to the uniform distribution for all input distributions D with entropy k > 0 if and only if the matrix A has no non-trivial invariant subspace (i.e., a non-zero subspace V \subsetneq \mathbb{F}_2^n such that AV \subseteq V). In other words, a matrix A yields an online linear extractor if and only if A has no non-trivial invariant subspace. For example, the linear transformation corresponding to multiplication by a generator of the field \mathbb{F}_{2^n} yields a good online linear extractor. Furthermore, for any such matrix convergence takes at most \widetilde{O}(n^2(k+1)/k^2) steps. We also study the more general notion of condensing—that is, we ask when this process converges to a distribution with entropy at least \ell, when the input distribution has entropy greater than k. (Extractors corresponding to the special case when \ell = n.) We show that a matrix gives a good condenser if there are relatively few vectors \mathbf{w} \in \mathbb{F}_2^n such that \mathbf{w}, A^T\mathbf{w}, \ldots, (A^T)^{n-k-1} \mathbf{w} are linearly dependent. As an application, we show that the very simple cyclic rotation transformation A(x_1,\ldots, x_n) = (x_n,x_1,\ldots, x_{n-1}) condenses to \ell = n-1 bits for any k > 1 if n is a prime satisfying a certain simple number-theoretic condition. Our proofs are Fourier-analytic and rely on a novel lemma, which gives a tight bound on the product of certain Fourier coefficients of any entropic distribution.
ePrint: https://eprint.iacr.org/2021/1002
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .