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 O(1) and round complexity 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 guaranteed output delivery (GOD). This is the first MPC protocol with the 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.
This is a joint work with Ivan Damgård (Aarhus University) and Arpita Patra, Shravani Patil (IISc Bangalore). The work is going to appear in the 24th IACR International Conference on Theory of Cryptography (TCC) 2026.
Brief bio: Ashish Choudhury is an Associate Professor in the Department of Computer Science and Engineering at the International Institute of Information Technology Bangalore (IIIT-B). He received his MS (by Research) and PhD degrees from IIT Madras, and subsequently held postdoctoral positions at the Indian Statistical Institute, Kolkata, and the University of Bristol. His research interests lie in secure multiparty computation and fault-tolerant distributed consensus. He has co-authored research monographs on secure multiparty computation and fault-tolerant distributed consensus with Prof. Arpita Patra. He has also offered MOOCs on Cryptography and Secure Computation through NPTEL.
