Paper 2025/1555

Statistical MPC with a Constant Communication Overhead

Ivan Damgård, Aarhus University

Shravani Patil, Indian Institute of Science Bangalore

Arpita Patra, Indian Institute of Science Bangalore

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.

@misc{cryptoeprint:2025/1555,
      author = {Ashish Choudhury and Ivan Damgård and Shravani Patil and Arpita Patra},
      title = {Statistical {MPC} with a Constant Communication Overhead},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/1555},
      year = {2025},
      url = {https://eprint.iacr.org/2025/1555}
}