Paper 2026/066 Original: eprint.iacr.org/2026/066 ↗

Complete Characterization of Randomness Extraction from DAG-Correlated Sources

Abstract

We introduce the SHEDAG (Somewhere Honest Entropic sources over Directed Acyclic Graphs) source model, a general framework for multi-block randomness sources with causal correlations. A SHEDAG source is defined over a directed acyclic graph (DAG) $G$, whose nodes output $n$-bit blocks. Honest nodes output mutually independent blocks, which are uniformly random by default and, more generally, may have high min-entropy. Corrupted nodes output arbitrary functions of their causal views (all predecessors in $G$). We tightly characterize the conditions under which zero-error and negligible-error randomness extraction from SHEDAG sources is possible. \begin{description} \item[Zero-error extraction:] We show that perfect extraction from SHEDAG sources with $t$ corruptions is possible if and only if $G$ contains an \emph{unrelated set} (an antichain under reachability) of size at least $t+1$. In particular, if every unrelated set has size at most $t$, no function can extract a perfectly uniform bit. We also give a polynomial-time algorithm for finding a maximum unrelated set, thereby efficiently determining the largest corruption threshold $t$ for which perfect extraction is possible. \item[Negligible-error extraction:] We introduce a graph parameter, called the \emph{resilience} of a DAG $G$, that characterizes the feasibility of randomness extraction with \emph{negligible} error in the block length. We define two variants of this parameter, $\res_\uni(G)$ and $\res_\ent(G)$, corresponding to uniform and entropic honest nodes, respectively. We show that when honest nodes are uniform, negligible-error extraction is impossible when the number of corrupted nodes $t>\res_\uni(G)$. When honest nodes are entropic, we show that negligible-error extraction is impossible when $t>\res_\ent(G)$. Complementing these impossibility results, we establish the following: \begin{itemize} \item[(i)] There exists an explicit extractor for SHEDAG sources with $t\leq \res_\uni(G)$ corrupted nodes and honest blocks that are uniform over $\bits^n$, achieving output length $\Omega_N(n)$ and error $2^{-\Omega_N(n)}$. Here $N$ is number of vertices of the DAG $G$. \item[(ii)] There exists a non-explicit extractor for SHEDAG sources with $t\leq \res_\ent(G)$ corrupted nodes and honest blocks of min-entropy $k\geq \poly\log n$, achieving output length $k^{\Omega(1)}$ and error $2^{-k^{\Omega(1)}}$. \end{itemize}