Paper 2026/2891

Multiparty Computation with Minimal Overhead without Circuit Transformation

Aditya Hegde, Johns Hopkins University
Phuoc Van Long Pham, Brown University
Mingyuan Wang, New York University Shanghai
Abstract

A central goal in secure multiparty computation (MPC) is to minimize the gap between the total computation performed by all parties and the cost of insecure circuit evaluation. In the honest majority setting, the ideal overhead of $\widetilde{\mathcal{O}}(1)$ is known to be achievable. However, all prior protocols over prime fields attaining this goal for general circuits relied on the so-called share packing techniques and, as a consequence, required prohibitively expensive circuit transformation steps to impose repetitive structure on the circuit. The only exception is the recent work of Garg, Jain, Mukherjee, and Wang (CRYPTO’24), which introduced a share unpacking technique and obtained the first such protocol without circuit transformation. However, their protocol only applies when the underlying field size is extraordinarily large, in particular, exponential in the *square* of the number of parties. In this work, we present the first MPC protocol with $\widetilde{\mathcal{O}}(1)$ overhead for any prime field $\mathbb{F}_p$ (more generally, any integer ring $\mathbb{Z}_p$) whose size is only required to be $n^{\Omega(n)}$, where $n$ is the number of parties (as opposed to $n^{\Omega(n^2)}$). Technically, we extend the unpacking approach of Garg et al. by developing a new approach to linear randomness extraction over integers, a tool that may be of independent interest.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A major revision of an IACR publication in CRYPTO 2026
DOI
https://doi.org/10.1007/978-3-032-35418-1_5
Contact author(s)
ahegde @ cs jhu edu
phuoc_pham_van_long @ brown edu
mingyuan wang @ nyu edu
History
2026-11-16: approved
2026-11-13: received
See all versions
Short URL
https://ia.cr/2026/2891
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2026/2891,
      author = {Aditya Hegde and Phuoc Van Long Pham and Mingyuan Wang},
      title = {Multiparty Computation with Minimal Overhead without Circuit Transformation},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/2891},
      year = {2026},
      doi = {https://doi.org/10.1007/978-3-032-35418-1_5},
      url = {https://eprint.iacr.org/2026/2891}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.