  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 plain model (no setup) with 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.
