High-Throughput Secure Multiparty Computation with an Honest Majority in Various Network Settings

In this work, we present novel protocols over rings for semi-honest secure three-party computation (3-PC) and malicious four-party computation (4-PC) with one corruption. Compared to state-of-the-art protocols in the same setting, our protocols require fewer low-latency and high-bandwidth links between the parties to achieve high throughput. Our protocols also reduce the computational complexity by requiring up to 50 percent fewer basic instructions per gate. Further, our protocols achieve the currently best-known communication complexity (3/5 elements per multiplication gate) with an optional preprocessing phase to reduce the communication complexity of the online phase to 2/3 elements per multiplication gate. In homogeneous network settings, i.e. all links between the parties share similar network bandwidth and latency, our protocols achieve up to two times higher throughput than state-of-the-art protocols. In heterogeneous network settings, i.e. all links between the parties share different network bandwidth and latency, our protocols achieve even larger performance improvements. We implemented our protocols and multiple other state-of-the-art protocols in a novel open-source C++ framework optimized for achieving high throughput. All our protocols achieve more than one billion 32-bit multiplication or more than 40 billion AND gates per second. This is the highest throughput achieved in 3-PC and 4-PC so far and more than three orders of magnitude higher than the throughput MP-SPDZ achieves in the same settings.