Paper 2021/1002

Online Linear Extractors for Independent Sources

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 AF2n×n, we study the convergence of the iterated process SASX, where XD is repeatedly sampled independently from some fixed (but unknown) distribution D with (min)-entropy at least k. Here, we think of S{0,1}n as the state of an online extractor, and X{0,1}n as its input. As our main result, we show that the state 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 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.

Metadata
Available format(s)
PDF
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
2021-07-28: received
Short URL
https://ia.cr/2021/1002
License
Creative Commons Attribution
CC BY

BibTeX

@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.