Improved Single-Round Secure Multiplication Using Regenerating Codes

Mark Abspoel, Ronald Cramer, Daniel Escudero, Ivan Damgård, Chaoping Xing

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

BibTeX
@article{abspoel2021improved,
  author = {Mark Abspoel and Ronald Cramer and Daniel Escudero and Ivan Damgård and Chaoping Xing},
  title = {{Improved Single-Round Secure Multiplication Using Regenerating Codes}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2021},
  url = {https://openreview.net/forum?id=rYp30yNd1PB},
}

Loading related content...

Figure