### Synchronous Perfectly Secure Message Transmission with Optimal Asynchronous Fallback Guarantees

##### Abstract

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)
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
Secure Message Transmission Multi-Party Computation Asynchronous Fallback
Contact author(s)
giovanni deligios @ inf ethz ch
chen-da liuzhang @ ntt-research com
History
2022-10-23: approved
See all versions
Short URL
https://ia.cr/2022/1397

CC BY

BibTeX

@misc{cryptoeprint:2022/1397,
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{https://eprint.iacr.org/2022/1397}},
url = {https://eprint.iacr.org/2022/1397}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.