Paper 2024/370
PerfectlySecure Multiparty Computation with Linear Communication Complexity over Any Modulus
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(nC)$, assuming that $q$ scales as $\Omega(n)$. However, for constantsize rings $\mathbb{Z}/q\mathbb{Z}$ where $q = O(1)$, the communication is actually $O(n\log nC)$ due to the need of the socalled ring extensions. In most natural settings, the number of parties is variable but the ``datatypes'' used for the computation are fixed (e.g. 64bit 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(nC)$, even for constantsize 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 secretsharing cannot work over constantsize 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 multiplicationfriendly 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 nonSIMD 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 secretsharing) group gates across the same layer, and not doing so, as in our work, leads to a unique set of challenges and complications.
Metadata
 Available format(s)
 Category
 Cryptographic protocols
 Publication info
 Preprint.
 Keywords
 Secure Multiparty ComputationPerfect SecurityCommunication Complexity
 Contact author(s)

daniel escudero @ protonmail com
yfsong @ mail tsinghua edu cn
wenhao wang @ yale edu  History
 20240317: revised
 20240229: received
 See all versions
 Short URL
 https://ia.cr/2024/370
 License

CC BY
BibTeX
@misc{cryptoeprint:2024/370, author = {Daniel Escudero and Yifan Song and Wenhao Wang}, title = {PerfectlySecure Multiparty Computation with Linear Communication Complexity over Any Modulus}, howpublished = {Cryptology ePrint Archive, Paper 2024/370}, year = {2024}, note = {\url{https://eprint.iacr.org/2024/370}}, url = {https://eprint.iacr.org/2024/370} }