Computationally Efficient Asynchronous MPC with Linear Communication and Low Additive Overhead

We explore the setting of asynchronous multi-party computation (AMPC) with optimal resilience $n=3t+1$, and develop an efficient protocol that optimizes both communication and computation.

The recent work by Goyal, Liu-Zhang, and Song [Crypto' 24] was the first to achieve AMPC with amortized linear communication cost without using computationally heavy public-key cryptography. However, its $\mathcal{O}(n^{14})$ additive communication overhead renders it impractical for most real-world applications.

It is possible to reduce the communication overhead significantly by leveraging cryptographic tools such as %random oracle hash, homomorphic commitments, public-key cryptography, or zero-knowledge proofs; however, the corresponding AMPC protocols introduce computation overhead of $\Omega(nC)$ public-key cryptographic operations that become bottleneck as $n$ grows. Overall, achieving AMPC with linear communication complexity, low additive communication overhead, and low computation overhead remains an open challenge.

In this work, we resolve this efficiency challenge by utilizing the random oracle model. By relying solely on computationally efficient primitives such as random oracle hash and symmetric-key cryptography, our protocol is not only efficient in terms of computation and communication overhead but also post-quantum secure. For a circuit with $C$ multiplication gates, our protocol achieves $\mathcal{O}(Cn)$ communication per multiplication gate with an additive overhead of $\mathcal{O}(n^4)$ communication. In terms of computation, our protocol only introduces an additive overhead of $\mathcal{O}(n^5)$ hash computations independent of the circuit size.