Synchronous Perfectly Secure Message Transmission with Optimal Asynchronous Fallback Guarantees

Giovanni Deligios and Chen-Da Liu Zhang

Financial Cryptography and Data Security, Springer Nature Switzerland, vol. , pp. 77–93, May 2023.

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, 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 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

BibTeX Citation

@inproceedings{DeLi23,
    author       = {Giovanni Deligios and {Chen-Da} {Liu Zhang}},
    title        = {Synchronous Perfectly Secure Message Transmission with Optimal Asynchronous Fallback Guarantees},
    editor       = {Baldimtsi, Foteini and Cachin, Christian},
    booktitle    = {Financial Cryptography and Data Security},
    pages        = {77--93},
    year         = {2023},
    month        = {5},
    address      = {Cham},
    publisher    = {Springer Nature Switzerland},
}