Yevgeniy Dodis, Siyao Guo, Noah Stephens-Davidowitz, and Zhiye Xie
Abstract
In this work, we characterize online linear extractors. In other words, given a matrix , we study the convergence of the iterated process , where is repeatedly sampled independently from some fixed (but unknown) distribution with (min)-entropy at least . Here, we think of as the state of an online extractor, and as its input.
As our main result, we show that the state converges to the uniform distribution for all input distributions with entropy if and only if the matrix has no non-trivial invariant subspace (i.e., a non-zero subspace such that ). In other words, a matrix yields an online linear extractor if and only if has no non-trivial invariant subspace. For example, the linear transformation corresponding to multiplication by a generator of the field yields a good online linear extractor. Furthermore, for any such matrix convergence takes at most 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 , when the input distribution has entropy greater than . (Extractors corresponding to the special case when .) We show that a matrix gives a good condenser if there are relatively few vectors such that are linearly dependent. As an application, we show that the very simple cyclic rotation transformation condenses to bits for any if 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.
@misc{cryptoeprint:2021/1002,
author = {Yevgeniy Dodis and Siyao Guo and Noah Stephens-Davidowitz 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},
url = {https://eprint.iacr.org/2021/1002}
}
Note: In order to protect the privacy of readers, eprint.iacr.org
does not use cookies or embedded third party content.