Paper 2023/1932

Multipars: Reduced-Communication MPC over Z2k

Abstract

In recent years, actively secure SPDZ-like protocols for dishonest majority, like SPD${\mathbb{Z}}_{2^k}$, Overdrive2k, and MHz2k, over base rings ${\mathbb{Z}}_{2^k}$ have become more and more efficient. In this paper, we present a new actively secure MPC protocol Multipars that outperforms these state-of-the-art protocols over $$ by more than a factor of 2 in the two-party setup in terms of communication. Multipars is the first actively secure N-party protocol over $$ that is based on linear homomorphic encryption (LHE) in the offline phase (instead of oblivious transfer or somewhat homomorphic encryption in previous works). The strong performance of Multipars relies on a new adaptive packing for BGV ciphertexts that allows us to reduce the parameter size of the encryption scheme and the overall communication cost. Additionally, we use modulus switching for further size reduction, a new type of enhanced CPA security over $$, a truncation protocol for Beaver triples, and a new LHE-based offline protocol without sacrificing over $$. We have implemented Multipars and therewith provide the fastest preprocessing phase over $$. Our evaluation shows that Multipars offers at least a factor of 8 lower communication costs and up to a factor of 15 faster runtime in the WAN setting compared to the currently best available actively secure MPC implementation over $$.