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). We propose a protocol with $n = 3t + 1$ for SIMD circuits with a communication overhead of ${\cal O}(1)$ and round complexity ${\cal O}(D)$ for circuit depth $D$, where $n$ is the number of parties and $t$ is the maximum number of corruptions. Moreover, our protocol achieves GOD. This is the first MPC protocol with above characteristics. 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.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- A major revision of an IACR publication in TCC 2026
- Keywords
- Information-theoretic MPCCommunication Complexity
- Contact author(s)
-
ashish choudhury @ iiitb ac in
ivan @ cs au dk
shravanip @ iisc ac in
arpita @ iisc ac in - History
- 2026-09-11: last of 3 revisions
- 2025-08-29: received
- See all versions
- Short URL
- https://ia.cr/2025/1555
- License
-
CC BY
BibTeX
@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}
}
