Dodis, Yevgeniy ;
Guo, Siyao ;
StephensDavidowitz, Noah ;
Xie, Zhiye
Online Linear Extractors for Independent Sources
Abstract
In this work, we characterize linear online extractors. In other words, given a matrix A ∈ F₂^{n×n}, we study the convergence of the iterated process S ← AS⊕X, where X∼D is repeatedly sampled independently from some fixed (but unknown) distribution D with (min)entropy k. Here, we think of S ∈ {0,1}ⁿ as the state of an online extractor, and X ∈ {0,1}ⁿ 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 nontrivial invariant subspace (i.e., a nonzero subspace V ⊊ F₂ⁿ such that AV ⊆ V). In other words, a matrix A yields a linear online 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 F_{2ⁿ} yields a good linear online extractor. Furthermore, for any such matrix convergence takes at most Õ(n²(k+1)/k²) 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 l, when the input distribution has entropy at least k. (Extractors corresponding to the special case when l = n.) We show that a matrix gives a good condenser if there are relatively few vectors w ∈ F₂ⁿ such that w, A^Tw, …, (A^T)^{nk}w are linearly dependent. As an application, we show that the very simple cyclic rotation transformation A(x₁,…, x_n) = (x_n,x₁,…, x_{n1}) condenses to l = 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.
BibTeX  Entry
@InProceedings{dodis_et_al:LIPIcs.ITC.2021.14,
author = {Dodis, Yevgeniy and Guo, Siyao and StephensDavidowitz, Noah and Xie, Zhiye},
title = {{Online Linear Extractors for Independent Sources}},
booktitle = {2nd Conference on InformationTheoretic Cryptography (ITC 2021)},
pages = {14:114:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771979},
ISSN = {18688969},
year = {2021},
volume = {199},
editor = {Tessaro, Stefano},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14333},
URN = {urn:nbn:de:0030drops143339},
doi = {10.4230/LIPIcs.ITC.2021.14},
annote = {Keywords: feasibility of randomness extraction, randomness condensers, Fourier analysis}
}
19.07.2021
Keywords: 

feasibility of randomness extraction, randomness condensers, Fourier analysis 
Seminar: 

2nd Conference on InformationTheoretic Cryptography (ITC 2021)

Issue date: 

2021 
Date of publication: 

19.07.2021 