Paper 2026/1105

Dishonest Majority Multi-Party Arithmetic Garbling with Constant Rate

Hanjun Li, Carnegie Mellon University

Elaine Shi, Carnegie Mellon University

Abstract

Minimizing round complexity is a central goal in secure Multi-Party Computation (MPC), particularly for deployment on high-latency networks. While constant-round protocols with concrete efficiency have been constructed, they are typically designed for Boolean circuits and each gate incurs a bandwidth cost linear in the security parameter. Moreover, for arithmetic-heavy applications such as privacy-preserving machine learning and statistical analysis, compiling arithmetic operations into Boolean gates incurs another substantial overhead in circuit size and communication. Conversely, existing arithmetic MPC protocols, such as SPDZ, require interaction rounds proportional to the circuit depth, imposing significant latency. In this work, we bridge this gap by presenting the first concretely-efficient maliciously-secure MPC protocol that achieves both constant-round and constant-rate communication, where the rate is defined as the bandwidth cost per party divided by the number of gates and the size of the values each gate operates on. Our protocol computes over bounded integers and is secure against a static, malicious adversary corrupting up to $n-1$ parties. The protocol is built upon the arithmetic garbling framework of Ball et al. (Eurocrypt 2023) and follows the BMR template, assuming the Decisional Composite Residuosity for the garbling phase and Learning Parity with Noise for preprocessing. We evaluate our protocol on matrix-vector multiplication, a fundamental operation for data analysis. For standard computation parameters, we reduce communication bandwidth by $101\times$ to $247\times$ and improves end-to-end runtime by $4.4\times$ to $10.7\times$ compared to state-of-the-art constant-round Boolean MPC baselines, even when accounting for the overhead of a full bit-decomposition on the output vector.

@misc{cryptoeprint:2026/1105,
      author = {Tianyao Gu and Hanjun Li and Elaine Shi},
      title = {Dishonest Majority Multi-Party Arithmetic Garbling with Constant Rate},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/1105},
      year = {2026},
      url = {https://eprint.iacr.org/2026/1105}
}