Yifan Song
, Tsinghua University, Shanghai Qi Zhi Institute
In this work, we study the communication complexity of constant-round MPC with guaranteed output delivery (GOD) in Minicrypt. We construct the first MPC protocol in this setting with linear communication complexity of $O(|C|n\kappa+Dn^3\kappa^3+W_I{\sf poly}(n,\kappa))$ bits under the assumption of a random oracle, where $|C|$ is the circuit size, $D$ is the circuit depth, $W_I$ is the number of input wires, and $\kappa$ is the security parameter. In comparison, the previously best-known construction with linear communication ($O(|C|n)$), presented by Goyal et al. (CRYPTO 2020), requires $O(D+n^2)$ round complexity. When targeting $O(D)$ round complexity, the best-known result by Agarwal et al. (ASIACRYPT 2024) still requires $O(|C|n^3)$ communication complexity. More communication is needed to achieve constant round complexity, even with non-black-box use of the underlying cryptographic primitives.
BibTeX
@misc{cryptoeprint:2026/1296,
author = {Junru Li and Yifan Song},
title = {Achieving Guaranteed Output Delivery {MPC} with Constant Rounds and Linear Communication in Minicrypt},
howpublished = {Cryptology {ePrint} Archive, Paper 2026/1296},
year = {2026},
url = {https://eprint.iacr.org/2026/1296}
}
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。