TL;DR
This paper introduces a novel multiparty computation (MPC) protocol that significantly reduces the number of communication rounds required for secure multiplication. By leveraging the power of regenerating codes over Galois rings, the authors achieve a single-round multiplication protocol with sub-quadratic communication complexity, a long-standing goal in the field.
What Problem Does This Paper Address?
Multiparty computation (MPC) allows multiple parties to jointly compute a function on their private data without revealing anything beyond the output. A crucial operation in MPC is secure multiplication, which typically requires multiple communication rounds. While existing protocols can achieve efficient communication, reducing the number of rounds is essential for improving performance, especially in scenarios with high network latency or dynamic participant sets (like blockchains). The paper addresses the challenge of achieving single-round secure multiplication with sub-quadratic communication complexity, particularly for the maximal adversary setting (where an adversary can corrupt up to half of the parties). Previous approaches either required more rounds or had higher communication costs.
Methods
The core of this work lies in the application of regenerating codes over Galois rings to MPC.
- Regenerating Codes: These codes, originally studied for distributed storage, have a "repair property" that allows reconstructing a secret from incomplete shares. The paper extends the theory of regenerating codes to Galois rings, a generalization of finite fields.
- Galois Rings: These are commutative rings with a multiplicative identity, generalizing finite fields and including rings like $\mathbb{Z}/p^k\mathbb{Z}$. This generalization allows the protocol to be more broadly applicable.
- Function-Dependent Preprocessing: The protocol utilizes preprocessing material that is tailored to the specific circuit being computed. This allows for more efficient online computation.
- Reverse Multiplication-Friendly Embeddings (RMFEs): These are used to efficiently pack multiple elements from a base ring into a larger Galois ring extension, enabling parallel computation.
- Single-Round Opening and Multiplication: The paper introduces protocols for efficiently opening secret-shared values using compressed shares and then uses this to build a single-round multiplication protocol.
- Protocol 2 (Consistency Check): To handle potential errors introduced by malicious parties (since compressed shares lack error detection), a separate protocol is introduced to batch-check the correctness of multiple openings at once.
Datasets
Not discussed in the paper. The paper focuses on theoretical constructions and protocols rather than empirical evaluation on specific datasets.
Key Insights and Ideas
- Regenerating Codes for MPC Rounds: The paper demonstrates that regenerating codes, previously explored for storage, can be effectively used to reduce the rounds of communication in MPC, not just the total communication volume.
- Galois Rings as a Powerful Generalization: Extending regenerating codes and MPC techniques to Galois rings broadens their applicability beyond finite fields, making them relevant for settings involving rings like $\mathbb{Z}/p^k\mathbb{Z}$.
- Single-Round Multiplication is Achievable: The work provides the first concrete application of regenerating codes to achieve single-round secure multiplication in the amortized setting with sub-quadratic communication, even for the maximal adversary.
- Trade-off Between Rounds and Communication: The paper highlights the fundamental trade-off in MPC between the number of rounds and communication complexity, showing how regenerating codes can be used to improve the former.
Key Results
- The paper presents an MPC protocol that evaluates a depth-$d$ arithmetic circuit in $d + O(1)$ rounds.
- The protocol achieves sub-quadratic communication complexity, specifically $O(n^2/\log(n))$ ring elements per multiplication gate in the amortized setting. This is a significant improvement over previous $O(n^2)$ bounds for single-round multiplication.
- The protocol is secure against an active adversary corrupting $t < n/2$ parties.
- The theoretical framework is extended to Galois rings, showing that Shamir's scheme over Galois rings also possesses the repair property.
Limitations and Future Work
- Amortized vs. Non-Amortized Setting: The presented results are primarily for the amortized setting (evaluating many circuits in parallel). The paper conjectures that achieving $o(n^2)$ complexity without amortization for single-round multiplication might be impossible.
- Active Security of Quintuple-Based Protocol: While the protocol is designed for active security, the paper notes that the security against an active adversary that introduces errors in compressed shares is not fully clear and leaves it as a question for future work. The level of redundancy in compressed shares for active security is an open problem.
- Maximal Adversary Constraint: The protocol is designed for the maximal adversary ($n=2t+1$). Further research could explore how these techniques might be adapted for different adversary thresholds.
- Generalization of Repair Property: While the paper characterizes linear repair for the 0-coordinate, the definition of regenerating codes typically includes repair for all coordinates. Future work could explore this more general definition.
Summary updated