Paper 2024/700

Sublinear Distributed Product Checks on Replicated Secret-Shared Data over $\mathbb{Z}_{2^k}$ without Ring Extensions

Yun Li, Tsinghua University
Daniel Escudero, J.P. Morgan AI Research & J.P. Morgan AlgoCRYPT CoE
Yufei Duan, Tsinghua University
Zhicong Huang, Ant Group
Cheng Hong, Ant Group
Chao Zhang, Tsinghua University
Yifan Song, Tsinghua University

Multiple works have designed or used maliciously secure honest majority MPC protocols over $\mathbb{Z}_{2^k}$ using replicated secret sharing (e.g. Koti et al. USENIX’21, and the references therein). A recent trend in the design of such MPC protocols is to first execute a semi-honest protocol, and then use a check that verifies the correctness of the computation requiring only sublinear amount of communication in terms of the circuit size. The so-called Galois ring extensions are needed in order to execute such checks over $\mathbb{Z}_{2^k}$, but these rings incur incredibly high computation overheads, which completely undermine any potential benefits the ring $\mathbb{Z}_{2^k}$ had to begin with. In this work we revisit the task of designing sublinear distributed product checks on replicated secret-shared data over $\mathbb{Z}_{2^k}$ among three parties with an honest majority. We present a novel technique for verifying the correctness of a set of multiplication (in fact, inner product) triples, involving a sublinear cost in terms of the amount of multiplications. Most importantly, unlike previous works, our tools entirely avoid Galois ring extensions, and only require computation over rings of the form $\mathbb{Z}_{2^l}$ . In terms of communication, our checks are 3∼5× lighter than existing checks using ring extensions, which is already quite remarkable. However, our most noticeable improvement is in terms of computation: avoiding extensions allows our checks to be 17.7∼44.2× better than previous approaches, for many parameter regimes of interest. Our experimental results show that checking a 10 million gate circuit with the 3PC protocol from (Boyle et al., CCS’19) takes about two minutes, while our approach takes only 2.82 seconds. Finally, our techniques are not restricted to the three-party case, and we generalize them to replicated secret-sharing with an arbitrary number of parties n. Even though the share size in this scheme grows exponentially with n, prior works have used it for n = 4 or n = 5—or even general n for feasibility results—and our distributed checks also represent improvements in these contexts.

Available format(s)
Cryptographic protocols
Publication info
Secure Multi-Party ComputationDistributed Product ChecksMalicious Security
Contact author(s)
liyun19 @ mails tsinghua edu cn
daniel escudero @ protonmail com
dyf23 @ mails tsinghua edu cn
zhicong hzc @ antgroup com
vince hc @ antgroup com
chaoz @ tsinghua edu cn
yfsong @ mail tsinghua edu cn
2024-05-10: approved
2024-05-07: received
See all versions
Short URL
Creative Commons Attribution


      author = {Yun Li and Daniel Escudero and Yufei Duan and Zhicong Huang and Cheng Hong and Chao Zhang and Yifan Song},
      title = {Sublinear Distributed Product Checks on Replicated Secret-Shared Data over $\mathbb{Z}_{2^k}$ without Ring Extensions},
      howpublished = {Cryptology ePrint Archive, Paper 2024/700},
      year = {2024},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.