This paper presents a groundbreaking advancement in secure multiparty computation (MPC), enabling multiple parties to jointly compute a function on their private inputs without revealing those inputs, even when the underlying mathematical structures (rings) are small and fixed. The key innovation is a protocol that achieves this perfect security with guaranteed output delivery using only linear communication complexity, a significant improvement over previous methods that required super-linear communication for such settings.
TL;DR
This paper introduces a novel MPC protocol that achieves perfect security and guaranteed output delivery with linear communication complexity, even for computations over small, fixed-size rings (like binary fields or rings of integers modulo 2^k). This is a significant improvement over prior work, which required super-linear communication in these practical settings. The protocol leverages a combination of advanced techniques like reverse multiplication-friendly embeddings and network routing to overcome the limitations of traditional MPC methods.
What Problem Does This Paper Address?
Secure multiparty computation (MPC) allows a group of parties to jointly compute a function on their private inputs while ensuring that only the final output is revealed, and nothing about the inputs themselves. A crucial aspect of MPC is its security guarantees, particularly against "active" adversaries who can deviate from the protocol. For a long time, achieving perfect security (meaning no statistical error, regardless of computational power) with guaranteed output delivery (G.O.D.) and linear communication complexity (where the total communication per party scales linearly with the size of the circuit being computed) was possible for computations over large finite fields or rings where the modulus was large (e.g., proportional to the number of parties).
However, for practical scenarios involving small, fixed-size rings (like binary fields F2 or rings Z/2^kZ for k=32 or 64), existing protocols required super-linear communication. This overhead was primarily due to the need for "ring extensions" to handle the limitations of secret-sharing schemes over small rings. This paper tackles the challenge of achieving linear communication complexity in these practically relevant, small-ring settings for general circuits (not just those with repetitive structures).
Methods
The paper's core contribution lies in a novel MPC protocol that achieves linear communication complexity over any modulus, including small, fixed-size rings. The key techniques employed are:
- Reverse Multiplication-Friendly Embeddings (RMFEs): These are crucial for efficiently "packing" multiple data elements into a single secret-shared value. This packing is essential for amortizing the cost of ring extensions, which are necessary for computations over small rings.
- Network Routing: This technique, adapted from recent work, allows for the efficient rearrangement of packed secret-shared values across different layers of a circuit. This is vital for handling general, non-SIMD (Single Instruction, Multiple Data) circuits where data dependencies can be complex.
- Optimistic Computation with Additive Secret Sharing: The protocol first performs computations "optimistically" using additive secret sharing, which is communication-efficient but not secure on its own.
- Verification with Shamir Secret Sharing: After the optimistic computation, a verification phase using Shamir secret sharing is performed. This phase uses the packed secret shares to check the correctness of the optimistic computation.
- Player Elimination Framework: To achieve guaranteed output delivery, the paper utilizes a party-elimination framework. If a party is found to be cheating, they are removed, and the computation can be restarted. This framework is carefully integrated to maintain linear communication.
- Galois Rings: The protocol operates over Galois rings, which are a generalization of finite fields and rings of integers modulo powers of primes, providing a unified framework for handling various moduli.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- Breaking the Logarithmic Overhead: The paper's central insight is how to overcome the logarithmic communication overhead typically associated with computations over small rings. This is achieved by cleverly packing data using RMFEs and efficiently routing it across circuit layers.
- Packing Across Layers: A significant technical contribution is the ability to pack elements that are distributed across different layers of the circuit, not just within the same layer as in previous packing techniques. This allows for more general circuit structures.
- Amortizing Ring Extension Costs: By packing multiple data elements into a single ring extension element, the protocol effectively amortizes the cost of these extensions, making them feasible for linear communication.
- Bridging the Gap to Practical Settings: The work directly addresses the limitations of existing MPC protocols in practical scenarios where fixed-size data types (like 64-bit integers) are common, and the underlying rings are small.
Key Results
The paper presents an MPC protocol with the following desirable features:
- Perfect Security: Against an active adversary corrupting $t < n/3$ parties.
- Any Modulus: Securely computes circuits over $Z/qZ$ for any constant $q$.
- Linear Communication Complexity: The total number of elements in $Z/qZ$ communicated scales as $O(|C| \cdot n + c \cdot n \cdot \log n + n^3 \cdot \log^2 n)$, where $|C|$ is the circuit size, $n$ is the number of parties, $c$ is the number of clients, and $t < n/3$. This is linear in $|C|$ for practical settings.
- Guaranteed Output Delivery (G.O.D.): Ensures the computation completes successfully.
Limitations and Future Work
- Complexity for SIMD Circuits: While the protocol handles general circuits, the paper notes that for SIMD circuits (where the same computation is applied to many data items), previous techniques might be more efficient.
- Addition Gate Overhead: The protocol incurs a linear communication cost for each addition gate, which is not the case in some other MPC protocols where addition gates are "free" in terms of communication. The authors suggest that avoiding this overhead would be an interesting future direction.
- Security with Abort: The paper focuses on the stronger notion of G.O.D. The authors acknowledge that achieving security with abort only (where a protocol might fail but not reveal information) with the same properties is still a challenging open question.
- Practical Implementation: While the theoretical results are significant, further work on practical implementation and performance optimization would be valuable.
Summary updated