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

Christopher Harth-Kitzerow, Ajith Suresh, Yongqin Wang, Hossein Yalame, Georg Carle, Murali AnnavaramarXiv 2022 · arXiv

TL;DR

This paper introduces Trio and Quad, two novel Secure Multiparty Computation (MPC) protocols designed to achieve record-breaking throughput in real-world, heterogeneous network environments. By drastically reducing local computational overhead and tolerating weak network links, the authors achieve over one billion 32-bit multiplications per second, outperforming existing frameworks by two to three orders of magnitude.

What Problem Does This Paper Address?

Secure Multiparty Computation (MPC) allows multiple parties to compute a function over their private inputs without revealing them. While theoretical research often focuses on minimizing total communication complexity, practical deployments face two major hurdles:

  1. Network Heterogeneity: In real-world cloud settings, network links between parties are rarely uniform. A single slow or high-latency link can bottleneck the entire protocol if it isn't designed to route around it.
  2. Computational Complexity: As network speeds increase (e.g., to 25 Gbit/s), the local CPU time required to process each "gate" in a circuit becomes the primary bottleneck. Existing protocols often require dozens of local operations per multiplication, which prevents them from saturating modern high-speed networks.

The authors aim to bridge the gap between theoretical efficiency and practical performance by designing protocols that are both "computation-light" and "network-aware."

Methods

The authors present two primary protocols and a high-performance C++ framework:

  • Trio (3PC): A semi-honest three-party protocol. It uses a novel sharing semantic that shifts a significant portion of the computational load to a preprocessing phase. This allows the online phase to remain extremely lean, requiring only two elements of communication per multiplication.
  • Quad (4PC): A maliciously secure four-party protocol (tolerating one corruption). Quad's key innovation is the use of two independent masks to hide secrets. This reduces the correlation between shares, allowing the protocol to compute a multiplication gate with less than half the basic instructions required by previous state-of-the-art protocols like Tetrad.
  • Heterogeneity Tolerance: Both protocols are designed to function efficiently even if most network links are weak. For instance, Quad can tolerate three low-bandwidth links and five high-latency links without a substantial performance drop.
  • High-Throughput Framework: The protocols are implemented in a new C++ framework that utilizes bitslicing, SIMD vectorization (AVX-2), and message buffering. These techniques allow the software to process thousands of gates in parallel, effectively utilizing modern CPU architectures.
Table 1: Operations and communication for multiplication

Datasets

The authors evaluated their work using several benchmarks across various simulated and real-world network settings:

  • Network Settings: LAN (0.3ms latency, 25 Gbit/s), MAN, WAN, and "Mixed" constellations using AWS C6in instances to capture real-world link variability.
  • Benchmarks:
    • Raw $Z_{2^{32}}$ multiplications and $Z_2$ (Boolean) AND gates.
  • AES-128 circuit (a standard MPC benchmark).
  • Large-scale vector-matrix products (common in privacy-preserving machine learning).

Key Insights and Ideas

  • Computation is the new bottleneck: The authors demonstrate that for high-speed networks (>250 Mbit/s), MPC tasks like scalar products become computation-bound rather than communication-bound. Runtimes for multiplications vs. scalar products. Scalar products plateau early, indicating a computational bottleneck.

  • Reducing Share Correlation: By moving from one mask to two in the 4PC setting, the authors found a way to simplify the local arithmetic needed for verification, which is the "secret sauce" behind Quad's speed.

  • Protocol-Level Load Balancing: Instead of trying to make every link fast, the authors designed the protocols so that the "heavy lifting" (bulk communication) happens over the strongest available links, while weak links are only used for non-latency-critical tasks like final verification.
Figure 1: Comparing Runtimes for Multiplications and Scalar Prod- uct with Varying Bandwidths

Key Results

The performance gains are substantial compared to established frameworks like MP-SPDZ or MOTION:

  • Peak Throughput: In a 25 Gbit/s LAN, the framework achieved over 1 billion 32-bit multiplications and over 32 billion AND gates per second.
  • Framework Comparison: The authors' implementation is 100x to 1000x faster than existing open-source frameworks for the same protocols (see Table 2). Throughput comparison across different MPC frameworks.

  • Real-World Speedup: In heterogeneous network settings (like WANs), the new protocols are up to 8x faster than previous state-of-the-art honest-majority protocols.

  • AES Performance: The implementation reached a throughput of 5-6 million AES blocks per second, roughly 4x higher than the previous record.
Table 2: Throughput in Gates/s for Various Frameworks

Limitations and Future Work

  • Honest Majority Only: The protocols are specifically designed for the honest-majority setting (3 or 4 parties with at most one corruption). They do not apply to the two-party or dishonest-majority settings, which are generally much slower.
  • Simple Corruptions: The work focuses on semi-honest (3PC) and malicious (4PC) security with abort. It does not address "guaranteed output delivery" where the protocol must finish even if a party actively disrupts it.
  • Future Directions: The authors suggest extending these high-throughput techniques to more complex non-linear functions required for advanced privacy-preserving machine learning, such as Sigmoid or Softmax activations.

Summary based on "High-Throughput Secure Multiparty Computation with an Honest Majority in Various Network Settings" by Harth-Kitzerow et al.

Summary updated

Abstract

In this work, we present novel protocols over rings for semi-honest secure three-party computation (3PC) and malicious four-party computation (4PC) with one corruption. While most existing works focus on improving total communication complexity, challenges such as network heterogeneity and computational complexity, which impact MPC performance in practice, remain underexplored. Our protocols address these issues by tolerating multiple arbitrarily weak network links between parties without any substantial decrease in performance. Additionally, they significantly reduce computational complexity by requiring up to half the number of basic instructions per gate compared to related work. These improvements lead to up to twice the throughput of state-of-the-art protocols in homogeneous network settings and up to eight times higher throughput in real-world heterogeneous settings. These advantages come at no additional cost: Our protocols maintain the best-known total communication complexity per multiplication, requiring 3 elements for 3PC and 5 elements for 4PC. We implemented our protocols alongside several state-of-the-art protocols (Replicated 3PC, ASTRA, Fantastic Four, Tetrad) in a novel open-source C++ framework optimized for high throughput. Five out of six implemented 3PC and 4PC protocols achieve more than one billion 32-bit multiplications or over 32 billion AND gates per second using our implementation in a 25 Gbit/s LAN environment. This represents the highest throughput achieved in 3PC and 4PC so far, outperforming existing frameworks like MP-SPDZ, ABY3, MPyC, and MOTION by two to three orders of magnitude.
BibTeX
@misc{harthkitzerow2022high,
  author = {Christopher Harth-Kitzerow and Ajith Suresh and Yongqin Wang and Hossein Yalame and Georg Carle and Murali Annavaram},
  title = {{High-Throughput Secure Multiparty Computation with an Honest Majority in Various Network Settings}},
  year = {2022},
  eprint = {2206.03776},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2206.03776},
}

Loading related content...

Figure