Paper 2018/540

Must the Communication Graph of MPC Protocols be an Expander?

Elette Boyle, Reichman University and NTT Research
Ran Cohen, Reichman University
Deepesh Data, Meta Platforms
Pavel Hubacek, Charles University

Secure multiparty computation (MPC) on incomplete communication networks has been studied within two primary models: (1) Where a partial network is fixed a priori, and thus corruptions can occur dependent on its structure, and (2) Where edges in the communication graph are determined dynamically as part of the protocol. Whereas a rich literature has succeeded in mapping out the feasibility and limitations of graph structures supporting secure computation in the fixed-graph model (including strong classical lower bounds), these bounds do not apply in the latter dynamic-graph setting, which has recently seen exciting new results, but remains relatively unexplored. In this work, we initiate a similar foundational study of MPC within the dynamic-graph model. As a first step, we investigate the property of graph expansion. All existing protocols (implicitly or explicitly) yield communication graphs which are expanders, but it is not clear whether this is inherent. Our results consist of two types (for constant fraction of corruptions): * Upper bounds: We demonstrate secure protocols whose induced communication graphs are not expander graphs, within a wide range of settings (computational, information theoretic, with low locality, even with low locality and adaptive security) each assuming some form of input-independent setup. * Lower bounds: In the setting without setup and adaptive corruptions, we demonstrate that for certain functionalities, no protocol can maintain a non-expanding communication graph against all adversarial strategies. Our lower bound relies only on protocol correctness (not privacy), and requires a surprisingly delicate argument. More generally, we provide a formal framework for analyzing the evolving communication graph of MPC protocols, giving a starting point for studying the relation between secure computation and further, more general graph properties.

Available format(s)
Cryptographic protocols
Publication info
A minor revision of an IACR publication in CRYPTO 2018
secure multiparty computationexpander graphcommunication locality
Contact author(s)
elette boyle @ runi ac il
cohenran @ runi ac il
deepesh data @ gmail com
hubacek @ iuuk mff cuni cz
2023-06-21: last of 5 revisions
2018-06-04: received
See all versions
Short URL
Creative Commons Attribution


      author = {Elette Boyle and Ran Cohen and Deepesh Data and Pavel Hubacek},
      title = {Must the Communication Graph of {MPC} Protocols be an Expander?},
      howpublished = {Cryptology ePrint Archive, Paper 2018/540},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.