Paper 2020/740

Always Have a Backup Plan: Fully Secure Synchronous MPC with Asynchronous Fallback

Erica Blum, Chen-Da Liu-Zhang, and Julian Loss


Protocols for secure Multi-Party Computation (MPC) can be classified according to the underlying communication model. Two prominent communication models considered in the literature are the synchronous and asynchronous models, which considerably differ in terms of the achievable security guarantees. Synchronous MPC protocols can achieve the optimal corruption threshold $n/2$ and allow every party to give input, but become completely insecure when synchrony assumptions are violated. On the other hand, asynchronous MPC protocols remain secure under arbitrary network conditions, but can tolerate only $n/3$ corruptions and parties with slow connections unavoidably cannot give input. A natural question is whether there exists a protocol for MPC that can tolerate up to $t_s < n/2$ corruptions under a synchronous network and $t_a < n/3$ corruptions even when the network is asynchronous. We answer this question by showing tight feasibility and impossibility results. More specifically, we show that such a protocol exists if and only if $t_a + 2t_s < n$ and the number of inputs taken into account under an asynchronous network is at most $n-t_s$.

Available format(s)
Cryptographic protocols
Publication info
Published by the IACR in CRYPTO 2020
multi-party computationsynchronousasynchronous
Contact author(s)
lichen @ inf ethz ch
2020-06-18: received
Short URL
Creative Commons Attribution


      author = {Erica Blum and Chen-Da Liu-Zhang and Julian Loss},
      title = {Always Have a Backup Plan: Fully Secure Synchronous MPC with Asynchronous Fallback},
      howpublished = {Cryptology ePrint Archive, Paper 2020/740},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.