Paper 2026/1156

Sub-Linear Secure Broadcast and Applications

Abstract

We present improved distributed broadcast and MST algorithms that are unconditionally secure against an eavesdropper controlling a fixed set of at most $f$ edges in an $n$-node $m$-edge $D$-diameter graph. We strive for secure algorithms with sublinear round and subquadratic message complexities (in $n$) for any $f$. This is in contrast to the exponential or polynomial dependence on $f$ in prior works. Our main results are: Secure broadcast algorithm, for sending an $O(\log n)$-bit message, that runs in $\tilde{O}(D+\sqrt{n})$ rounds and $\tilde{O}(n^{3/2})$ messages. This matches the state-of-the-art bounds for \emph{insecure} broadcast by [Ghaffari and Kuhn, and Gmyr and Pandurangan, DISC 2018]. Our bounds also improve over the $\tilde{O}(D+\sqrt{f n})$-round complexity and $\tilde{O}(\sqrt{f n}\cdot m)$ message complexity of secure broadcast by [Hitron, Parter and Yogev, DISC 2022]. Secure MST algorithm with sublinear round and subcubic message complexities that improve over the algorithm by [Hitron, Parter and Yogev, ITCS 2023] in the entire regime. In particular, when $f=\Theta(n)$, we improve the round complexity from $\tilde O(n^{3/2})$ to $\tilde O(n^{2/3})$, and the message complexity from $\tilde O(n^{3})$ to $\tilde O(n^{7/3})$. Our algorithms are randomized and their correctness and (statistical) security hold with high probability. The algorithms are based on a combination of techniques: Karger's sampling, tree packing and sparse recovery sketches.