TL;DR
This paper introduces TURBOPACK, a novel protocol for secure multiparty computation (MPC) that significantly reduces the communication overhead during the "online" phase, making it constant regardless of the number of parties involved. This is a crucial advancement for practical MPC, especially when dealing with many participants, as it directly impacts the responsiveness and efficiency of computations.
What Problem Does This Paper Address?
Secure multiparty computation (MPC) allows multiple parties to jointly compute a function on their private inputs without revealing those inputs to each other, except for the final output. A key challenge in MPC is minimizing the amount of data that needs to be exchanged between parties, known as communication complexity. This is particularly critical in the "honest majority" setting (where more than half of the parties are honest), where information-theoretic security is achievable. While previous works have focused on reducing overall communication, the online phase of an MPC protocol (the part that happens after initial setup and directly impacts latency) has remained a bottleneck, often requiring communication that scales linearly with the number of parties. This paper addresses the need for an MPC protocol with a constant, and concretely small, online communication complexity, even for a maximal honest majority adversary.
Methods
TURBOPACK leverages a combination of techniques to achieve its efficiency:
- Packed Secret Sharing: This core technique allows multiple secrets to be bundled together and processed as a single unit. This is a standard approach for reducing communication, but TURBOPACK uses it in a novel way to achieve constant online communication.
- Offline/Online Paradigm: The protocol, like many modern MPC systems, splits computation into two phases: an offline phase (preprocessing) that can be done in advance and is independent of inputs, and an online phase that is input-dependent and dictates latency. TURBOPACK optimizes the online phase significantly.
- Circuit-Dependent Preprocessing: The protocol allows for some preprocessing to be tailored to the specific circuit being computed. This enables further optimization of the online phase by preparing specific random values that are then consumed efficiently.
- Packed Beaver Triples: This technique, adapted from prior work, is used to efficiently compute multiplications in the online phase.
What's new is how these techniques are combined to achieve a constant online communication complexity, even for the maximal honest majority setting (where the adversary can corrupt up to t = (n-1)/2 parties), and with significantly smaller constants than previous attempts. The authors also introduce an optimization that further reduces communication by a factor of 2 in the circuit-dependent preprocessing phase.
Datasets
Not discussed in the paper. The evaluation is based on experimental performance with synthetic circuits.
Key Insights and Ideas
- Constant Online Communication is Achievable and Practical: The paper demonstrates that it's possible to break the linear dependency of online communication on the number of parties, a significant step towards truly practical MPC for large-scale deployments.
- Smart Preprocessing Unlocks Online Efficiency: By allowing circuit-dependent preprocessing, TURBOPACK can prepare specific random values that are then consumed with minimal communication in the online phase.
- Balancing Offline and Online Costs: While TURBOPACK excels in the online phase, its overall communication (including preprocessing) is higher than some state-of-the-art protocols. This highlights a common trade-off in MPC design, where optimizing one phase might increase another. The paper argues this trade-off is acceptable for applications prioritizing low latency.
- Simplicity Matters: The authors emphasize that TURBOPACK is concretely simple and avoids complex network routing or permutation tools, which can be a practical advantage over other protocols that achieve similar theoretical bounds.
Key Results
- Online Communication: TURBOPACK achieves a constant online communication complexity of 12 field elements per multiplication gate, independent of the number of parties (
n). This is a significant improvement over prior works that requiredO(n)communication. - Circuit-Dependent Preprocessing: This phase requires 8 field elements per gate.
- Circuit-Independent Preprocessing: This phase requires 10n + 24 field elements per gate.
- Experimental Speedups: The implementation shows significant speedups in the online phase compared to an optimized DN07 protocol. For example, with 45 parties and a circuit of depth 10, TURBOPACK's online phase was up to 5x faster. In some scenarios, improvements of up to 6.7x were observed.
- Malicious Security: The protocol can be compiled to achieve malicious security with only a slight increase in communication complexity.
Limitations and Future Work
- Overall Communication: While the online phase is highly optimized, the total communication complexity (including preprocessing) is higher than some state-of-the-art protocols like ATLAS. The authors acknowledge this gap but argue it's a worthwhile trade-off for the online gains.
- Experimental Setup: The experiments were conducted on a single machine using inter-process communication to simulate distributed environments. While this setup is reproducible, it might not perfectly reflect the dynamics of a truly distributed system, especially concerning context switching overheads for a large number of parties.
- Future Work: The authors suggest that using more efficient libraries for polynomial computation and linear algebra could further improve the protocol's performance and reduce the overhead. They also mention that their optimization for the circuit-dependent preprocessing phase could be further explored.
Summary updated