The Crypto Seminar

"Must the Communication Graph of MPC Protocols be an Expander?"

Ran Cohen

Monday, September 17, 2018 at 12:00 Noon

Room 506 (CIT - 5th Floor)

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):

  1. Upper bounds: We demonstrate secure protocols whose induced communication graphs are not expander graphs, within a wide range of settings.
  2. Lower bounds: In the setting without setup and with adaptive corruptions, we demonstrate that for certain functionalities, no protocol can maintain a non-expanding communication graph against all adversarial strategies.

This is a joint work with Elette Boyle, Deepesh Data, and Pavel Hubacek. Ran is a post-doctoral researcher at MIT CSAIL and Northeastern University hosted by Prof. Shafi Goldwasser and Prof. Abhi Shelat. He spent a year as a post-doctoral researcher in the Theory of Computation Group at Tel Aviv University hosted by Prof. Iftach Haitner. He completed his Ph.D. in the Cryptography Research Group at Bar-Ilan University under the supervision of Prof. Yehuda Lindell. His research interests are in cryptography, with a focus on secure multiparty computation.

Host: Professor Seny Kamara