International Association for Cryptologic Research

International Association
for Cryptologic Research


Network-Agnostic Security Comes (Almost) for Free in DKG and MPC

Renas Bacho , CISPA Helmholtz Center for Information Security
Daniel Collins , EPFL
Chen-Da Liu-Zhang , NTT Research
Julian Loss , CISPA Helmholtz Center for Information Security
DOI: 10.1007/978-3-031-38557-5_3 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: CRYPTO 2023
Abstract: Distributed key generation (DKG) protocols are an essential building block for threshold cryptosystems. Many DKG protocols tolerate up to t_s<n/2 corruptions assuming a well-behaved synchronous network, but become insecure as soon as the network delay becomes unstable. On the other hand, solutions in the asynchronous model operate under arbitrary network conditions, but only tolerate t_a<n/3 corruptions, even when the network is well-behaved. In this work, we ask whether one can design a protocol that achieves security guarantees in either scenario. We show a complete characterization of _network-agnostic_ DKG protocols, showing that the tight bound is t_a + 2t_s < n. As a second contribution, we provide an optimized version of the network-agnostic MPC protocol by Blum, Liu-Zhang and Loss [CRYPTO'20] which improves over the communication complexity of their protocol by a linear factor. Moreover, using our DKG protocol, we can instantiate our MPC protocol in the _plain PKI model_, i.e., without the need to assume an expensive trusted setup. Our protocols incur comparable communication complexity as state-of-the-art DKG and MPC protocols with optimal resilience in their respective purely synchronous and asynchronous settings, thereby showing that network-agnostic security comes (almost) _for free_.
  title={Network-Agnostic Security Comes (Almost) for Free in DKG and MPC},
  author={Renas Bacho and Daniel Collins and Chen-Da Liu-Zhang and Julian Loss},