(2026-06) Achieving Guaranteed Output Delivery MPC with Constant Rounds and Linear Communication in Minicrypt
2026-06-21
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 bits under the assumption of a random oracle, where is the circuit size, is the circuit depth, is the number of input wires, and is the security parameter.
In comparison, the previously best-known construction with linear communication (), presented by Goyal et al. (CRYPTO 2020), requires round complexity. When targeting round complexity, the best-known result by Agarwal et al. (ASIACRYPT 2024) still requires communication complexity. More communication is needed to achieve constant round complexity, even with non-black-box use of the underlying cryptographic primitives.