TL;DR
This paper introduces a new protocol for secure multiparty computation (MPC) that significantly reduces the number of communication rounds required for multiplication. By leveraging a novel application of "regenerating codes" over Galois rings, they achieve a single-round multiplication protocol with sub-quadratic communication complexity, a long-standing goal in the field.
What Problem Does This Paper Address?
In secure multiparty computation (MPC), multiple parties want to jointly compute a function on their private data without revealing anything beyond the output. A crucial operation in MPC is secure multiplication, which is often performed gate-by-gate. Standard MPC protocols require a number of communication rounds proportional to the depth of the circuit being computed. While reducing communication complexity has been a major focus, minimizing the number of rounds, especially for single-round multiplication, has remained a significant challenge. Existing protocols for single-round multiplication typically incur a quadratic communication cost in the number of parties, which is undesirable. This paper aims to bridge this gap by developing a single-round secure multiplication protocol with improved communication complexity, particularly for the challenging case of a maximal adversary.
Methods
The core of this work lies in the application of "regenerating codes" to MPC. The authors extend the theory of regenerating codes to Galois rings, which are a generalization of finite fields. They then use this extended theory to develop a protocol that allows for efficient reconstruction of secret-shared values using compressed shares.
Key techniques include:
- Regenerating Codes over Galois Rings: The paper generalizes the concept of regenerating codes, which have a "repair property," to Galois rings. This property is crucial for reconstructing secrets from incomplete shares.
- Function-Dependent Preprocessing: The protocol utilizes function-dependent preprocessing, where random sharings are generated specifically for each multiplication gate. This is a departure from generic preprocessing methods and allows for better efficiency.
- Reverse Multiplication-Friendly Embeddings (RMFEs): RMFEs are used to embed elements from a base ring into a larger Galois ring extension. This allows for parallel computations and helps achieve the desired communication complexity.
- Single-Round Opening Protocol: A novel protocol is presented for opening secret-shared values using compressed shares, which is essential for the single-round multiplication.
- Protocol for Secure Multiplication: The paper combines these techniques to construct a single-round secure multiplication protocol. This protocol involves opening compressed shares and then performing computations in the Galois ring.
- Security Model: The protocol is proven secure in the Universal Composability (UC) model against an active adversary corrupting a minority of parties.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- Regenerating codes are not just for storage: While regenerating codes were initially explored for distributed storage, this paper demonstrates their significant utility in reducing communication rounds for secure computation.
- Galois rings are a powerful generalization: Extending the theory of regenerating codes to Galois rings, rather than just finite fields, opens up new possibilities for MPC protocols, especially for rings like $\mathbb{Z}/p^k\mathbb{Z}$ which are gaining popularity.
- Single-round multiplication is achievable with sub-quadratic communication: The paper tackles the open problem of achieving single-round multiplication with better than $O(n^2)$ communication complexity, a significant improvement.
- Function-dependent preprocessing is key: Tailoring preprocessing to specific multiplication gates, rather than using generic triples, is crucial for achieving the desired efficiency and security.
- The "repair property" is central: The ability to reconstruct secrets from compressed shares (the repair property) is the fundamental mechanism enabling the round reduction.
Key Results
- Single-round secure multiplication: The paper presents a protocol that evaluates a depth-$d$ arithmetic circuit in $d+O(1)$ rounds.
- Sub-quadratic communication: The protocol achieves $o(n^2)$ ring elements communicated per multiplication gate in the amortized setting. Specifically, they achieve $O(n^2/\log(n))$ ring elements.
- Security against active adversaries: The protocol is statistically secure against an active adversary corrupting a minority of parties ($t < n/2$).
- Generalization to Galois rings: The theoretical framework is extended to Galois rings, making it applicable to a broader range of cryptographic settings.
Limitations and Future Work
- Amortized setting: The primary result is achieved in the amortized setting (parallel evaluations). The authors conjecture that achieving $o(n^2)$ complexity without amortization for single-round multiplication might be impossible.
- Active security of quintuple-based protocol: The active security of the quintuple-based protocol (used for multiplication) is not fully clear, especially regarding the impact of compressed shares on error detection. The authors leave this as future work.
- Non-amortized setting: Whether the $o(n^2)$ complexity can be achieved in the non-amortized setting is left as an open problem.
- Further exploration of regenerating codes: The authors suggest that their work on regenerating codes over Galois rings could be beneficial for other areas, such as exploring potentially fruitful directions in MPC.
Summary updated