Paper 2025/1699

A Constant-Rate Compiler for MPC over Noisy Networks

Carmit Hazay, Bar-Ilan University

Manuj Mukherjee, Indraprastha Institute of Information Technology (IIIT) Delhi

Jaspal Singh, Purdue University West Lafayette, Georgia Institute of Technology

Arun Yeragudipati

Vassilis Zikas, Georgia Institute of Technology

Abstract

The study of efficient multi-party computation (MPC) has been a central focus of cryptographic research, leading to a broad range of techniques across diverse practical models. However, the vast majority of this work assumes reliable communication channels and largely ignores network-level noise, a fundamental characteristic of modern communication systems. In this work we study information-theoretic MPC over noisy networks in the multi-party setting. We construct an $n$-party MPC protocol that is secure against semi-honest adversaries corrupting a majority of the parties assuming all communication is carried over BSC channels with a fixed bit-flip probability. Our construction incurs only constant-factor communication overhead compared to the underlying MPC protocol over noiseless channels: specifically, it computes any circuit $C$ with communication complexity $O(n^2(|C|+\kappa))$, where $\kappa$ is a statistical security parameter. This substantially improves the naive approach, which can only guarantee super-linear communication, namely, $O(n^2|C|(\kappa+\log |C|))$. To achieve this result, we introduce a novel multi-party interactive coding scheme tailored to cryptographic protocols that rely on correlated randomness. We show that combining this coding scheme with the classical GMW protocol yields a noise-resilient MPC protocol that preserves its security guarantees while incurring only linear overhead. A central technical challenge we address is a subtle correctness issue that arises in the simulation of protocols with correlated randomness: without careful synchronization, different parties may use inconsistent correlated randomness for what is logically the same protocol step, causing the computation to fail even in the absence of noise. Our novel interactive coding scheme ensures that all parties use consistent correlated randomness in every simulated round of the MPC. Surprisingly, this issue also affects the two-party simulation over noisy channels [Gelles, Paskin-Cherniavsky, and Zikas, SCN’18], leaving an unaddressed gap in its analysis. Our techniques provide a way to resolve this gap.

@misc{cryptoeprint:2025/1699,
      author = {Ran Gelles and Carmit Hazay and Manuj Mukherjee and Jaspal Singh and Arun Yeragudipati and Vassilis Zikas},
      title = {A Constant-Rate Compiler for {MPC} over Noisy Networks},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/1699},
      year = {2025},
      url = {https://eprint.iacr.org/2025/1699}
}