## Abstract

In this work, we characterize linear online extractors. In other words, given a matrix A ∈ F^{n}_{2}^{×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}^{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 V ⊆ F^{n}_{2} 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 F2n yields a good linear online extractor. Furthermore, for any such matrix convergence takes at most O^{e}(n^{2}(k + 1)/k^{2}) 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 at least k. (Extractors corresponding to the special case when ℓ = n.) We show that a matrix gives a good condenser if there are relatively few vectors w ∈ F^{n}_{2} such that w, A^{T} w,..., (A^{T} )^{n}−^{k}w are linearly dependent. As an application, we show that the very simple cyclic rotation transformation A(x1,..., xn) = (xn, x1,..., xn−1) condenses to ℓ = 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.

Original language | English (US) |
---|---|

Title of host publication | 2nd Conference on Information-Theoretic Cryptography, ITC 2021 |

Editors | Stefano Tessaro |

Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |

ISBN (Electronic) | 9783959771979 |

DOIs | |

State | Published - Jul 1 2021 |

Event | 2nd Conference on Information-Theoretic Cryptography, ITC 2021 - Virtual, Bertinoro, Italy Duration: Jul 23 2021 → Jul 26 2021 |

### Publication series

Name | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|

Volume | 199 |

ISSN (Print) | 1868-8969 |

### Conference

Conference | 2nd Conference on Information-Theoretic Cryptography, ITC 2021 |
---|---|

Country/Territory | Italy |

City | Virtual, Bertinoro |

Period | 7/23/21 → 7/26/21 |

## Keywords

- Feasibility of randomness extraction
- Fourier analysis
- Randomness condensers

## ASJC Scopus subject areas

- Software