Paper 2021/1002
Online Linear Extractors for Independent Sources
Yevgeniy Dodis, Siyao Guo, Noah StephensDavidowitz, and 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 nontrivial invariant subspace (i.e., a nonzero 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 nontrivial 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 condensingthat 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)^{nk1} \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_{n1})$ condenses to $\ell = n1$ bits for any $k > 1$ if $n$ is a prime satisfying a certain simple numbertheoretic condition. Our proofs are Fourieranalytic and rely on a novel lemma, which gives a tight bound on the product of certain Fourier coefficients of any entropic distribution.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Published elsewhere. MINOR revision.ITC 2021
 DOI
 10.4230/LIPIcs.ITC.2021.14
 Keywords
 extractorscondensorsentropy accumulationRNGs
 Contact author(s)

noahsd @ gmail com
zx572 @ nyu edu
dodis @ cs nyu edu
siyao guo @ nyu edu  History
 20210728: received
 Short URL
 https://ia.cr/2021/1002
 License

CC BY
BibTeX
@misc{cryptoeprint:2021/1002, author = {Yevgeniy Dodis and Siyao Guo and Noah StephensDavidowitz and Zhiye Xie}, title = {Online Linear Extractors for Independent Sources}, howpublished = {Cryptology ePrint Archive, Paper 2021/1002}, year = {2021}, doi = {10.4230/LIPIcs.ITC.2021.14}, note = {\url{https://eprint.iacr.org/2021/1002}}, url = {https://eprint.iacr.org/2021/1002} }