### More Efficient Dishonest Majority Secure Computation over $\mathbb{Z}_{2^k}$ via Galois Rings

##### Abstract

In this work we present a novel actively secure multiparty computation protocol in the dishonest majority setting, where the computation domain is a ring of the type $\mathbb{Z}_{2^k}$. Instead of considering an "extension ring" of the form $\mathbb{Z}_{2^{k+\kappa}}$ as in SPD$\mathbb{Z}_{2^k}$ (Cramer et al, CRYPTO 2018) and its derivatives, we make use of an actual ring extension, or more precisely, a Galois ring extension $\mathbb{Z}_{p^k}[\mathtt{X}]/(h(\mathtt{X}))$ of large enough degree, in order to ensure that the adversary cannot cheat except with negligible probability. These techniques have been used already in the context of honest majority MPC over $\mathbb{Z}_{p^k}$, and to the best of our knowledge, our work constitutes the first study of the benefits of these tools in the dishonest majority setting. Making use of Galois ring extensions requires great care in order to avoid paying an extra overhead due to the use of larger rings. To address this, reverse multiplication-friendly embeddings (RMFEs) have been used in the honest majority setting (e.g. Cascudo et al, CRYPTO 2018), and more recently in the dishonest majority setting for computation over $\mathbb{Z}_2$ (Cascudo and Gundersen, TCC 2020). We make use of the recent RMFEs over $\mathbb{Z}_{p^k}$ from (Cramer et al, CRYPTO 2021), together with adaptations of some RMFE optimizations introduced in (Abspoel et al, ASIACRYPT 2021) in the honest majority setting, to achieve an efficient protocol that only requires in its online phase $12.4k(n-1)$ bits of amortized communication complexity and one round of communication for each multiplication gate. We also instantiate the necessary offline phase using Oblivious Linear Evaluation (OLE) by generalizing the approach based on Oblivious Transfer (OT) proposed in MASCOT (Keller et al, CCS 2016). To this end, and as an additional contribution of potential independent interest, we present a novel technique using Multiplication-Friendly Embeddings (MFEs) to achieve OLE over Galois ring extensions using black-box access to an OLE protocol over the base ring $\mathbb{Z}_{p^k}$ without paying a quadratic cost in terms of the extension degree. This generalizes the approach in MASCOT based on Correlated OT Extension. Finally, along the way we also identify a bug in a central proof in MASCOT, and we implicitly present a fix in our generalized proof.

Available format(s)
Category
Cryptographic protocols
Publication info
Published elsewhere. CRYPTO 2022
Keywords
Multiparty Computation Rings Dishonest Majority RMFE
Contact author(s)
daniel escudero @ protonmail com
xingcp @ sjtu edu cn
chen_yuan @ sjtu edu cn
History
2022-06-23: revised
See all versions
Short URL
https://ia.cr/2022/815

CC BY

BibTeX

@misc{cryptoeprint:2022/815,
author = {Daniel Escudero and Chaoping Xing and Chen Yuan},
title = {More Efficient Dishonest Majority Secure Computation over $\mathbb{Z}_{2^k}$ via Galois Rings},
howpublished = {Cryptology ePrint Archive, Paper 2022/815},
year = {2022},
note = {\url{https://eprint.iacr.org/2022/815}},
url = {https://eprint.iacr.org/2022/815}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.