Lund et al. (JACM 1992) invented the powerful Sumcheck protocol that has been extensively used in complexity theory and in designing concretely efficient (zero-knowledge) arguments. In this work, we systematically study Sumcheck in the context of secure multi-party computation (MPC). Our main result is a new unified framework for lifting semi-honest MPC protocols to maliciously secure ones, with a small constant multiplicative overhead in both computation and communication. In general, our approach applies to any semi-honest, linear secret-sharing based dishonest majority MPC secure up to additive attacks, where linear secret-sharing can be enhanced with an authentication mechanism. At a high-level, our approach has a highly distributive flavor, where the parties jointly emulate a Sumcheck prover to prove the correctness of MPC semi-honest evaluations in zero-knowledge, while simultaneously emulating a Sumcheck verifier to verify the proof themselves. Equipped with our new techniques, we design a SPDZ-style MPC protocol with \(5N+O(\log {N})\) online communication per party and sublinear preprocessing based on efficient pseudorandom correlation generators (PCGs), where N is the circuit size. This substantially improves the 6N communication achieved in Le Mans (CRYPTO 2022), the state-of-the-art in the SPDZ line of works. Technically, the savings are obtained by using a Sumcheck-based mechanism to check N unverified authenticated multiplication triple relations, which requires only \(N+1\) standard Beaver triples and \(O(\log {N})\) random authenticated shares, rather than N additional unverified authenticated triples needed by a “sacrifice” strategy. We also show concrete benefits for honest majority MPC protocols based on Shamir secret sharing. Compared to the best known approach in this scenario (Goyal et al. CRYPTO 2020) based on fully linear interactive oracle proofs (FLIOPs), asymptotically we achieve the same O(N) additive overhead in computation and \(O(\log {N})\) additive overhead in communication. However, we replace the \(O(\log {N})\) double sharings used there with \(O(\log {N})\) random sharings, and reduce the soundness error from \(O(\frac{N}{|\mathbb {F}|})\) to \(O(\frac{\log {N}}{|\mathbb {F}|})\) , where \(\mathbb {F}\) is the underlying field.

On the Power of Sumcheck in Secure Multiparty Computation

会议论文
发表日期：

2026年

查看全文

Zhe Li,
Chaoping Xing,
Yizhou Yao,
Chen Yuan

摘要

Lund et al. (JACM 1992) invented the powerful Sumcheck protocol that has been extensively used in complexity theory and in designing concretely efficient (zero-knowledge) arguments. In this work, we systematically study Sumcheck in the context of secure multi-party computation (MPC). Our main result is a new unified framework for lifting semi-honest MPC protocols to maliciously secure ones, with a small constant multiplicative overhead in both computation and communication. In general, our approach applies to any semi-honest, linear secret-sharing based dishonest majority MPC secure up to additive attacks, where linear secret-sharing can be enhanced with an authentication mechanism. At a high-level, our approach has a highly distributive flavor, where the parties jointly emulate a Sumcheck prover to prove the correctness of MPC semi-honest evaluations in zero-knowledge, while simultaneously emulating a Sumcheck verifier to verify the proof themselves. Equipped with our new techniques, we design a SPDZ-style MPC protocol with \(5N+O(\log {N})\) online communication per party and sublinear preprocessing based on efficient pseudorandom correlation generators (PCGs), where N is the circuit size. This substantially improves the 6N communication achieved in Le Mans (CRYPTO 2022), the state-of-the-art in the SPDZ line of works. Technically, the savings are obtained by using a Sumcheck-based mechanism to check N unverified authenticated multiplication triple relations, which requires only \(N+1\) standard Beaver triples and \(O(\log {N})\) random authenticated shares, rather than N additional unverified authenticated triples needed by a “sacrifice” strategy. We also show concrete benefits for honest majority MPC protocols based on Shamir secret sharing. Compared to the best known approach in this scenario (Goyal et al. CRYPTO 2020) based on fully linear interactive oracle proofs (FLIOPs), asymptotically we achieve the same O(N) additive overhead in computation and \(O(\log {N})\) additive overhead in communication. However, we replace the \(O(\log {N})\) double sharings used there with \(O(\log {N})\) random sharings, and reduce the soundness error from \(O(\frac{N}{|\mathbb {F}|})\) to \(O(\frac{\log {N}}{|\mathbb {F}|})\) , where \(\mathbb {F}\) is the underlying field.