RoundRole: Unlocking the Efficiency of Multi-party Computation with Bandwidth-aware Execution

RoundRole: Unlocking the Efficiency of Multi-party Computation with Bandwidth-aware Execution

Speakers: Xiaoyu Fan

Conference: NDSS Symposium

YouTube: https://www.youtube.com/watch?v=w03Ew6RpRgQ

Overview

Secure multi-party computation (MPC) is fundamentally constrained by network communication: modern CPUs process data at 30-100 GB/s, while typical wide-area networks offer only 100 Mbps to 1 Gbps, leaving CPUs idle waiting for data. The MPC community has made significant progress reducing total data volume and communication rounds, but this talk reveals an overlooked side effect: these optimizations often create asymmetric communication patterns where bandwidth utilization is severely unbalanced across parties. The researchers introduce RoundRole, an automatic execution-level optimizer that decouples logical roles from physical nodes, rotating role assignments across parallel tasks to achieve nearly 100% bandwidth utilization -- delivering significant performance speedups across six protocols and six network configurations.

Background

▶ Watch: The CPU-to-network speed gap: why MPC is communication-bound (0:00)

Secure multi-party computation (MPC) allows multiple parties to jointly compute a function on private inputs without revealing the underlying data, typically using secret sharing where inputs are split into random shares and processed with specific protocols. The communication required to maintain privacy and correctness is the primary performance bottleneck.

The MPC community has extensively optimized algorithmic complexity -- reducing total data volume and round counts. However, the researchers discovered that these optimizations often produce protocols where the amount of data sent and received is not equally distributed among parties. For example, in a three-party fixed-point multiplication protocol, one party might receive zero bytes while the other two have 50% of their sending capacity wasted because they are constrained by their peers' receiving capacities. In total, only about one-third of available network bandwidth is actually utilized.

This asymmetry exists across many common MPC operations including fixed-point multiplication, arithmetic-to-boolean conversion, and shuffling. The execution is only as fast as the most burdened link, meaning significant bandwidth capacity is simply left on the table.

Key Findings

▶ Watch: Core idea: decouple logical roles from physical nodes (4:00)

The core insight is that logical MPC roles can be decoupled from physical nodes. Instead of assigning each physical server a fixed role for the entire computation, RoundRole splits the protocol into multiple parallel tasks and rotates logical role assignments across physical nodes:

Bandwidth Waste Quantified: Analysis of several common MPC operations showed that sending and receiving volumes vary significantly between parties. In fixed-point multiplication, approximately two-thirds of available bandwidth is wasted.

Near-Perfect Utilization: By balancing loads through role rotation, RoundRole achieves nearly 100% bandwidth utilization across all physical nodes, with no single node's bandwidth wasted while others sit idle.

Consistent Speedups: Testing across six different protocols and six unique network settings (including both homogeneous and heterogeneous bandwidth configurations, from 100 Mbps to 10 Gbps), RoundRole consistently improved performance regardless of the specific protocol or network environment.

Input-Size Independence: The profiling stage captures protocol communication patterns independently of input size, making RoundRole adaptable to any protocol and physical node configuration without re-profiling for different workloads.

Technical Deep Dive

▶ Watch: RoundRole optimizer: profiling, modeling, and execution strategy (4:30)

RoundRole operates as an automatic execution-level optimizer with three stages:

Stage 1 - Profiling and Modeling: Given a protocol description and physical bandwidth measurements, RoundRole captures input-size-independent characteristics including communication patterns (how much each logical role sends/receives), optimal workload allocation rates, and the relationship between protocol communication and available bandwidth. Two function parameters are modeled to capture execution efficiency relative to the underlying physical nodes.

Stage 2 - Role Mapping: The workload is divided into tasks (T1, T2, T3, etc.). For each task, physical nodes take on different logical roles. In task one, node N1 might be party P1; in task two, N1 takes the role of P2. When aggregated across parallel tasks, the overall communication pattern balances out, ensuring no single node is a bottleneck.

Stage 3 - Execution Strategy: Given input sizes, RoundRole automatically decides the execution strategy including the number of tasks and the corresponding role mapping for each task. This decision adapts to the specific combination of protocol and physical network configuration.

The approach is purely an execution-level optimization -- it does not modify the underlying MPC protocols or their security properties. The protocols remain unchanged; only the mapping of logical roles to physical nodes is optimized across parallel task instances.

Demo / Proof of Concept

▶ Watch: Results: consistent speedups across six protocols and six networks (6:00)

The researchers evaluated RoundRole across six protocols (including multiplication and shuffling) and six network configurations spanning 100 Mbps to 10 Gbps bandwidth, with both homogeneous and heterogeneous settings. Results showed consistent performance speedups across all combinations. The improvement comes directly from exploiting the originally wasted bandwidth of asymmetric communication protocols by cleverly allocating roles based on bandwidth and protocol patterns, pushing execution closer to the theoretical limits of the hardware.

Defensive Implications

▶ Watch: Summary: optimizing MPC is a multi-angle systems problem (7:00)

RoundRole's contribution is primarily to the efficiency of privacy-preserving computation rather than direct security defense. However, the performance implications are relevant for practical MPC deployment:

Making MPC Practical: By significantly reducing execution time through better bandwidth utilization, RoundRole helps close the gap between theoretical MPC capabilities and practical deployment requirements. Faster MPC enables organizations to use privacy-preserving computation for real-time or near-real-time applications.

Protocol-Agnostic Optimization: Because RoundRole works at the execution level without modifying protocols, it can be applied to any existing MPC protocol. This means security teams can adopt new, more secure protocols without worrying about execution-level performance optimization -- RoundRole handles that automatically.

WAN Deployment: The bandwidth-aware approach is particularly valuable for wide-area network deployments where bandwidth is scarce and variable, which is the common deployment scenario for cross-organizational privacy-preserving computation.

Key Takeaways

• State-of-the-art MPC protocol optimizations often create asymmetric communication patterns that waste up to two-thirds of available bandwidth
• RoundRole decouples logical MPC roles from physical nodes, rotating assignments across parallel tasks to achieve nearly 100% bandwidth utilization
• The approach is protocol-agnostic and works across both homogeneous and heterogeneous network configurations
• Performance improvements are consistent across six protocols and six network settings, from 100 Mbps to 10 Gbps
• Profiling is input-size independent, enabling adaptation to any protocol and physical configuration without re-profiling
• The optimization is purely at the execution level and does not modify the underlying MPC protocols or their security properties

About the Speaker(s)

Xiaoyu Fan is among the authors from Tsinghua University, with collaborators from the Shanghai Qi Zhi Institute and iQroup. The talk was presented by Wing Yang, a PhD candidate at the University of Washington, on behalf of the authors who could not attend due to visa issues. The research focuses on systems-level optimization of MPC, bridging the gap between algorithmic complexity improvements and practical deployment performance.