Synchronous Perfectly Secure Message Transmission with Optimal Asynchronous Fallback Guarantees

Secure message transmission (SMT) constitutes a fundamental network-layer building block for distributed protocols over incomplete networks. More specifically, a sender $$\textbf{S}$$ and a receiver $$\textbf{R}$$ are connected via $$\ell $$ disjoint paths, a subset of which are controlled by the adversary. Perfectly-secure SMT protocols in synchronous and asynchronous networks are resilient up to $$\ell /2$$ and $$\ell /3$$ corruptions respectively. In this work, we ask whether it is possible to achieve a perfect SMT protocol that simultaneously tolerates $$t_s < \ell /2$$ corruptions when the network is synchronous, and $$t_a < \ell /3$$ when the network is asynchronous. We completely resolve this question by showing that perfect SMT is possible if and only if $$2t_a + t_s < \ell $$ . In addition, we provide a concretely round-efficient solution for the (slightly worse) trade-off $$t_a + 2t_s < \ell $$ . As a direct application of these results, following the recent work by Appan, Chandramouli, and Choudhury [PODC’22], we obtain an n-party perfectly-secure multi-party computation protocol with asynchronous fallback over any network with connectivity $$\ell $$ , as long as $$t_a + 3t_s