Achieving Guaranteed Output Delivery MPC with Constant Rounds and Linear Communication in Minicrypt

본문 미리보기

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-kn