Welcome to the resource topic for 2025/177
Title:
On the Power of Sumcheck in Secure Multiparty Computation
Authors: Zhe Li, Chaoping Xing, Yizhou Yao, Chen Yuan
Abstract:Lund et al. (JACM 1992) invented the powerful Sumcheck protocol that has been extensively used in complexity theory and also for 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 generic framework for lifting semi-honest MPC protocols to malicious security, with a {\em constant} multiplicative overhead in {\em both} computation and communication, and even additional logarithmic communication in the best case. In general, our approach applies to any semi-honest linear secret-sharing based MPC secure up to additive attacks, where secret-sharings can be added with an authentication property. At a high-level, our approach has a highly distributive flavor, where the parties jointly emulate a Sumcheck prover that proves the correctness of MPC semi-honest evaluations in zero-knowledge, meanwhile they also jointly emulate a Sumcheck verifier and verify the proof themselves. Along the way, we provide a new angle of view on the {\em fully linear interactive oracle proof} (FLIOP) systems proposed by Boneh et al. (CRYPTO 2019). That is, essentially distributed sumcheck on proving a batch of multiplications is an optimized concrete instantiation of the FLIOP-based approach.
As concrete applications of our techniques, we first consider semi-honest MPC protocols based on Shamir secret-sharing with an honest majority. Suppose M-party and circuit size N, to achieve malicious security, our approach only introduces additional 10MN+O(M\log{N}) total computation, communication of reconstructions of 4\log{N}+6 secret-shared values, O(\log{N}) rounds and O(\log{N}) correlated randomness. This shows that malicious security with abort in honest majority MPC comes {\em free} in terms of both computation and communication.
We then consider dishonest majority MPC, where the best known semi-honest protocol achieves 2N online communication per party and sublinear preprocessing by using programmable pseudorandom correlation generators (PCGs). We realize malicious MPC with 4N+O(\log{N}) online communication as well as sublinear preprocessing, matching the optimal 2\times communication overhead in Hazay et al. (JOC 2024). Our protocol is essentially obtained by using Sumcheck techniques to check authenticated multiplication triple relations, which requires only N+1 {\em standard Beaver triples} and O(\log{N}) random authenticated shares for N semi-honestly generated authenticated triples. Compared to the FLIOP-based checking mechanism (Boyle et al. CRYPTO 2022) that requires O(\sqrt{N}) communication and O(N^{1.5}) computation, we do not introduce any cryptographic assumption beyond PCGs, and have O(N) computation.
ePrint: https://eprint.iacr.org/2025/177
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .