Paper 2023/096

MPC With Delayed Parties Over Star-Like Networks

Mariana Gama, COSIC, KU Leuven
Emad Heydari Beni, COSIC, KU Leuven, Nokia Bell Labs, Antwerp
Emmanuela Orsini, Bocconi University
Nigel P. Smart, COSIC, KU Leuven, Zama Inc
Oliver Zajonc, COSIC, KU Leuven

While the efficiency of secure multi-party computation protocols has greatly increased in the last few years, these improvements and protocols are often based on rather unrealistic, idealised, assumptions about how technology is deployed in the real world. In this work we examine multi-party computation protocols in the presence of two major constraints present in deployed systems. Firstly, we consider the situation where the parties are connected not by direct point-to-point connections, but by a star-like topology with a few central post-office style relays. Secondly, we consider MPC protocols with a strong honest majority ($n \gg t/2$) in which we have stragglers (some parties are progressing slower than others). We model stragglers by allowing the adversary to delay messages to and from some parties for a given length of time. We first show that having only a single honest rely is enough to ensure consensus of the messages sent within a protocol; secondly, we show that special care must be taken to describe multiplication protocols in the case of relays and stragglers and that some well known protocols do not guarantee privacy and correctness in this setting; thirdly, we present an efficient honest-majority MPC protocol which can be run on top of the relays and which provides active-security with abort in the case of a strong honest majority, even when run with stragglers. We back up our protocol presentation with both experimental evaluations and simulations of the effect of the relays and delays on our protocol.

Available format(s)
Cryptographic protocols
Publication info
A major revision of an IACR publication in ASIACRYPT 2023
MPCStar Networks
Contact author(s)
mariana botelhodagama @ kuleuven be
emad heydari_beni @ nokia-bell-labs com
emmanuela orsini @ unibocconi it
nigel smart @ kuleuven be
oliver zajonc @ esat kuleuven be
2023-09-13: last of 2 revisions
2023-01-26: received
See all versions
Short URL
Creative Commons Attribution


      author = {Mariana Gama and Emad Heydari Beni and Emmanuela Orsini and Nigel P. Smart and Oliver Zajonc},
      title = {{MPC} With Delayed Parties Over Star-Like Networks},
      howpublished = {Cryptology ePrint Archive, Paper 2023/096},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.