Paper 2026/320

Statistically Secure Asynchronous MPC with Linear Communication and $\mathcal{O}(n^5)$ Additive Overhead

Abstract

Secure multiparty computation (MPC) allows distrusted parties to jointly evaluate a common function while keeping their inputs private. In this work, we focus on improving the communication complexity of information-theoretic asynchronous MPC with optimal resilience ($t < n/3$). The current state-of-the-art work in this setting by Goyal, Liu-Zhang, and Song [Crypto’24] achieves amortized linear communication per gate with $\mathcal{O}(n^{14}\kappa)$ field elements additive overhead, where $\kappa$ is the security parameter. In comparison, the best-known result in the synchronous setting by Goyal, Song, and Zhu [Crypto’20] achieves amortized linear communication per gate with only $\mathcal{O}(n^{6})$ field elements additive overhead, revealing a significant gap that we aim to close. This work closes this gap and goes further. We present the first statistically secure asynchronous MPC protocol achieving amortized linear communication per gate with only $\mathcal{O}(n^{5})$ field elements additive overhead assuming a functionality for Agreement on Common Set (ACS). With the best-known instantiation for ACS, we obtain an asynchronous MPC protocol in the plain model with additive overhead $\mathcal{O}(n^5)$ field elements in expectation. In the setting of statistical security with optimal resilience, this even surpasses the best synchronous result. Technically, our contributions include (i) a new protocol for generating Beaver triples with linear communication per triple and $\mathcal{O}(n^3)$ field elements additive overhead assuming functionalities for generating random degree-$t$ Shamir sharings and ACS, and (ii) a new protocol for generating random degree-$t$ Shamir sharings with linear communication per sharing and $\mathcal{O}(n^{5})$ field elements additive overhead assuming a functionality for ACS. Along the way, we also construct a new protocol for asynchronous complete secret sharing (ACSS) with linear communication per sharing and $\mathcal{O}(n^5)$ field elements additive overhead, and a parallel version of ACSS that maintains the same additive overhead assuming a functionality for ACS, which may be of independent interest.

Note: In the previous version of this paper, our ACSS construction only supported the distribution of random degree-t sharings by an honest dealer, and we incorrectly claimed that it was sufficient to realize the ACSS functionality. Nevertheless, this construction is sufficient to realize the RandSh functionality, which only requires an honest dealer to distribute random degree-t sharings, and thus our main result remains unaffected. In the current version, we fix this issue by providing an ACSS construction that supports the distribution of arbitrary degree-t sharings. We also update the ACS instantiation, improving the overall additive overhead of AMPC from O((\kappa+n)n^4) to O(n^5) field elements in expectation.