International Association
for Cryptologic Research

We present two unconditionally secure asynchronous multiparty computation (AMPC) protocols among n parties with an amortized communication complexity of O(n) field elements per multiplication gate and which can tolerate a computationally unbounded active adversary corrupting t< n /4 parties. These are the first AMPC protocols with linear communication complexity per multiplication gate. Our first protocol is statistically secure in a completely asynchronous setting and improves on the previous best AMPC protocol in the same setting by a factor of \\Theta(n). Our second protocol is perfectly secure in a hybrid setting, where one round of communication

is assumed to be synchronous and improves on the previous best AMPC protocol in the hybrid setting by a factor of \\Theta(n^2).

The central contribution common to both the protocols is a new, simple and communication efficient, albeit natural framework for the preprocessing (offline) phase that is used to generate sharings of random multiplication triples, to be used later for the circuit evaluation. The framework is built on two new components, both of which are instantiated robustly: the first component allows the parties to verifiably share random multiplication triples. The second component allows the parties to securely extract sharings of random multiplication triples from a set of sharings of multiplication triples, verifiably shared by individual parties. Our framework is simple and does not involve either of the existing somewhat complex, but popular techniques, namely player elimination and dispute control, used in the preprocessing phase of most of the existing protocols. The framework is of independent interest and can be adapted to other MPC scenarios to improve the overall round complexity.