Paper 2026/2891
Multiparty Computation with Minimal Overhead without Circuit Transformation
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
-
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}
}