Paper 2025/1555

Statistical MPC with a Constant Communication Overhead

Abstract

We study the feasibility of constant communication-overhead statistically-secure MPC tolerating malicious adversaries in the synchronous setting and guaranteed output delivery (GOD). The results of Damgård et al. (CRYPTO 2019) say that there exists an arithmetic circuit $C$ such that any statistically-secure MPC for securely evaluating $C$ with $n = 2t+s$ parties, where $s > 0$, requires a communication complexity of $\Theta(\frac{n|C|}{s})$ bits. To match the above lower bound for $s = t+ 1$, we propose a protocol for SIMD circuits with a communication complexity of $O(|C|\kappa)$ bits, for a statistical security parameter $\kappa$ and round complexity $O(D)$ for circuit depth $D$. Moreover, our protocol achieves the highest notion of security, namely GOD. This is the first constant-overhead statistically-secure MPC protocol with optimal resilience, GOD and $O(D)$ rounds. To design our protocol, we give two major contributions. Our first technical contribution is a verifiable secret sharing (VSS) protocol that achieves constant per-secret overhead via two-dimensional packing. Our second contribution is a constant-overhead degree-reduction protocol that converts a high-degree packed sharing into a lower-degree packed sharing.