Paper 2024/370

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

Daniel Escudero, J.P. Morgan AI Research & J.P. Morgan AlgoCRYPT CoE
Yifan Song, Institute for Theoretical Computer Science, Institute for Interdisciplinary Information Sciences, Tsinghua University, Shanghai Qi Zhi Institute
Wenhao Wang, Yale University

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.

Available format(s)
Cryptographic protocols
Publication info
Secure Multiparty ComputationPerfect SecurityCommunication Complexity
Contact author(s)
daniel escudero @ protonmail com
yfsong @ mail tsinghua edu cn
wenhao wang @ yale edu
2024-03-17: revised
2024-02-29: received
See all versions
Short URL
Creative Commons Attribution


      author = {Daniel Escudero and Yifan Song and Wenhao Wang},
      title = {Perfectly-Secure Multiparty Computation with Linear Communication Complexity over Any Modulus},
      howpublished = {Cryptology ePrint Archive, Paper 2024/370},
      year = {2024},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.