Online linear extractors for independent sources
2nd Conference on Information-Theoretic Cryptography (ITC 2021), 2021•drops.dagstuhl.de
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.
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.
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.
drops.dagstuhl.de