Synchronous Perfectly Secure Message Transmission with Optimal Asynchronous Fallback Guarantees

Giovanni Deligios; Chen-Da Liu-Zhang

Paper 2022/1397

Synchronous Perfectly Secure Message Transmission with Optimal Asynchronous Fallback Guarantees

Giovanni Deligios, ETH Zurich

Chen-Da Liu-Zhang, NTT Research

Abstract

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

Note: Updated Related Work

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Published elsewhere. Financial Cryptography and Data Security 2023
Keywords: Secure Message Transmission Multi-Party Computation Asynchronous Fallback Network Agnostic
Contact author(s): giovanni deligios @ inf ethz ch
chen-da liuzhang @ ntt-research com
History: 2023-10-09: last of 2 revisions; 2022-10-15: received; See all versions
Short URL: https://ia.cr/2022/1397
License: 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},
      url = {https://eprint.iacr.org/2022/1397}
}