License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITC.2021.14
URN: urn:nbn:de:0030-drops-143339
Go to the corresponding LIPIcs Volume Portal

Dodis, Yevgeniy ; Guo, Siyao ; Stephens-Davidowitz, Noah ; Xie, Zhiye

Online Linear Extractors for Independent Sources

LIPIcs-ITC-2021-14.pdf (0.7 MB)


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 non-trivial invariant subspace (i.e., a non-zero 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 non-trivial 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)^{n-k}w are linearly dependent. As an application, we show that the very simple cyclic rotation transformation A(x₁,…, x_n) = (x_n,x₁,…, x_{n-1}) condenses to l = 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.

BibTeX - Entry

  author =	{Dodis, Yevgeniy and Guo, Siyao and Stephens-Davidowitz, Noah and Xie, Zhiye},
  title =	{{Online Linear Extractors for Independent Sources}},
  booktitle =	{2nd Conference on Information-Theoretic Cryptography (ITC 2021)},
  pages =	{14:1--14:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-197-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{199},
  editor =	{Tessaro, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-143339},
  doi =		{10.4230/LIPIcs.ITC.2021.14},
  annote =	{Keywords: feasibility of randomness extraction, randomness condensers, Fourier analysis}

Keywords: feasibility of randomness extraction, randomness condensers, Fourier analysis
Collection: 2nd Conference on Information-Theoretic Cryptography (ITC 2021)
Issue Date: 2021
Date of publication: 19.07.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI