Maintaining Sublinear Locality Over Time: Adaptively Secure MPC on a Reusable Hidden Graph

Communication locality of an $n$-party protocol measures the maximum degree of the communication graph induced by the protocol execution. While secure multi-party computation (MPC) with small, sublinear locality exists in the static-corruption setting, this goal seems nearly paradoxical in the adaptive-corruption setting: Even against fail-stop adversaries, small neighbour sets of honest parties lie vulnerable to identification and corruption.

Surprisingly, Chandran et al. [ITCS '15] showed that for a single MPC execution, sublinear locality and adaptive security can be simultaneously achieved, assuming honest-to-honest channels are hidden from the adversary. Their solution works in the ``hidden-graph model,'' where a fresh, initially hidden, low-degree graph is being used in each round. In turn, the combined degree grows with every round---inherently limiting the approach to a single-shot MPC execution, and sublinear total rounds. This raises the following question, which is the focus of our work:

Is it possible to maintain sublinear locality over an unbounded number of executions facing adaptive adversaries?

In this work, we provide an affirmative answer in two settings:

First, we consider semi-honest adversaries and information-theoretic security, and construct reusable MPC with polylog($n$) locality.

Second, we consider fail-stop adversaries and computational security, and construct reusable MPC with $\tilde O(n^{2/3})$ locality.

Our results are obtained by devising low-locality protocols while hiding important information about the graph topology, enabling the parties to reuse a single hidden graph. As an independent contribution, this serves as new results for adaptively secure topology-hiding computation (Moran, Orlov, Richelson [TCC '15]).