Perfectly-Secure Multiparty Computation with Linear Communication Complexity over Any Modulus

Daniel Escudero, Yifan Song, Wenhao Wang

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

Abstract

Consider the task of secure multiparty computation (MPC) among $n$ parties with perfect security and guaranteed output delivery, supporting $t<n/3$ active corruptions. Suppose the arithmetic circuit $C$ to be computed is defined over a finite ring $\mathbb{Z}/q\mathbb{Z}$, for an arbitrary $q\in\mathbb{Z}$. It is known that this type of MPC over such ring is possible, with communication that scales as $O(n|C|)$, assuming that $q$ scales as $\Omega(n)$. However, for constant-size rings $\mathbb{Z}/q\mathbb{Z}$ where $q = O(1)$, the communication is actually $O(n\log n|C|)$ due to the need of the so-called ring extensions. In most natural settings, the number of parties is variable but the "datatypes" used for the computation are fixed (e.g. 64-bit integers). In this regime, no protocol with linear communication exists. In this work we provide an MPC protocol in this setting: perfect security, G.O.D. and $t<n/3$ active corruptions, that enjoys linear communication $O(n|C|)$, even for constant-size rings $\mathbb{Z}/q\mathbb{Z}$. This includes as important particular cases small fields such as $\mathbb{F}_2$, and also the ring $\mathbb{Z}/2^k\mathbb{Z}$. The main difficulty in achieving this result is that widely used techniques such as linear secret-sharing cannot work over constant-size rings, and instead, one must make use of ring extensions that add $\Omega(\log n)$ overhead, while packing $\Omega(\log n)$ ring elements in each extension element in order to amortize this cost. We make use of reverse multiplication-friendly embeddings (RMFEs) for this packing, and adapt recent techniques in network routing (Goyal et al. CRYPTO'22) to ensure this can be efficiently used for non-SIMD circuits. Unfortunately, doing this naively results in a restriction on the minimum width of the circuit, which leads to an extra additive term in communication of $\mathsf{poly}(n)\cdot\mathsf{depth}(C)$. One of our biggest technical contributions lies in designing novel techniques to overcome this limitation by packing elements that are distributed across different layers. To the best of our knowledge, all works that have a notion of packing (e.g. RMFE or packed secret-sharing) group gates across the same layer, and not doing so, as in our work, leads to a unique set of challenges and complications.
BibTeX
@article{escudero2024perfectly,
  author = {Daniel Escudero and Yifan Song and Wenhao Wang},
  title = {{Perfectly-Secure Multiparty Computation with Linear Communication Complexity over Any Modulus}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2024},
  doi = {10.1007/978-981-96-0938-3\_4},
}
Figure