Breaking the O(n|C|) Barrier for Unconditionally Secure Asynchronous Multiparty Computation

In PODC 2012, Dani et al. presented an unconditionally secure multiparty computation (MPC) protocol, which allows a set of n parties to securely evaluate any arithmetic circuit C of size |C| on their private inputs, even in the presence of a computationally unbounded malicious adversary who can corrupt upto t<(13−ϵ)n parties, for any given non-zero ε with 0<ϵ<13. The total circuit-dependent communication complexity of their protocol is O(\ensuremathPolyLog(n)⋅|C|), which is a significant improvement over the standard MPC protocols, which has circuit-dependent complexity of the form O(\ensuremathPoly(n)⋅|C|). The key innovation in their protocol is that instead of following the standard method of having every party communicate with every other party for evaluating each gate of C, it is sufficient to involve only a small subset of parties of size Θ(PolyLog(n)) to communicate with each other for evaluating each gate of the circuit. The protocol was presented in a synchronous setting and it was left as an open problem to design an asynchronous MPC (AMPC) protocol, with a similar characteristic. In this work, we solve this open problem by presenting the first unconditionally secure AMPC protocol where the circuit dependent complexity is O(\ensuremathPolyLog(n)⋅|C|)