(2026-05) Maintaining Sublinear Locality Over Time; Adaptively Secure MPC on a Reusable Hidden Graph
2026-05-08
Communication locality of an -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() locality.
Second, we consider fail-stop adversaries and computational security, and construct reusable MPC with 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]).