Paper 2022/1397

Synchronous Perfectly Secure Message Transmission with Optimal Asynchronous Fallback Guarantees

Giovanni Deligios, ETH Zurich
Chen-Da Liu-Zhang, NTT Research

Secure message transmission (SMT) constitutes a fundamental network-layer building block for distributed protocols over incomplete networks. More specifically, a sender $\mathbf{S}$ and a receiver $\mathbf{R}$ are connected via $\ell$ disjoint paths, of which at most $t$ paths are controlled by the adversary. \emph{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 our results, following the recent work by Appan, Chandramouli, and Choudhury [PODC'22], we obtain an $n$-party perfectly-secure synchronous multi-party computation protocol with asynchronous fallback over any network with connectivity $\ell$, as long as $t_a + 3t_s <n$ and $2t_a + t_s < \ell$.

Available format(s)
Cryptographic protocols
Publication info
Secure Message Transmission Multi-Party Computation Asynchronous Fallback
Contact author(s)
giovanni deligios @ inf ethz ch
chen-da liuzhang @ ntt-research com
2022-10-23: approved
2022-10-15: received
See all versions
Short URL
Creative Commons Attribution


      author = {Giovanni Deligios and Chen-Da Liu-Zhang},
      title = {Synchronous Perfectly Secure Message Transmission with Optimal Asynchronous Fallback Guarantees},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1397},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.