Condensing Against Online Adversaries

We investigate the task of deterministically condensing randomness from Online Non-Oblivious Symbol Fixing (oNOSF) sources, a natural model for which extraction is impossible [AORSV, EUROCRYPT'20]. A $(g,\ell)$-oNOSF source is a sequence of $\ell$ blocks where at least $g$ of the blocks are good (independent and have some min-entropy) and the remaining bad blocks are controlled by an online adversary where each bad block can be arbitrarily correlated with any block that appears before it. The existence of condensers was studied in [CGR, FOCS'24]. They proved condensing impossibility results for various values of $g, \ell$ and showed the existence of condensers matching the impossibility results in the case when $n$ is extremely large compared to $\ell$. In this work, we make significant progress on proving the existence of condensers with strong parameters in almost all parameter regimes, even when $n$ is a large enough constant and $\ell$ is growing. This almost resolves the question of the existence of condensers for oNOSF sources, except when $n$ is a small constant. We construct the first explicit condensers for oNOSF sources, achieve parameters that match the existential results of [CGR, FOCS'24], and obtain an improved construction for transforming low-entropy oNOSF sources into uniform ones. We find applications of our results to collective coin flipping and sampling, well-studied problems in fault-tolerant distributed computing. We use our condensers to provide simple protocols for these problems. To understand the case of small $n$, we focus on $n=1$ which corresponds to online non-oblivious bit-fixing (oNOBF) sources. We initiate a study of a new, natural notion of influence of Boolean functions which we call online influence. We establish tight bounds on the total online influence of Boolean functions, implying extraction lower bounds.
Comment: 36 pages