Maintaining Sublinear Locality Over Time: Adaptively Secure MPC on a Reusable Hidden Graph
Published in Eurocrypt 2026, 2026
Abstract
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 Õ(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 et al. [TCC ’15]).