Paper 2025/177

On the Power of Sumcheck in Secure Multiparty Computation

Abstract

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 generic framework for lifting semi-honest MPC protocols to maliciously secure ones, with a {\em constant} multiplicative overhead in {\em both} computation and communication, and in the best case, only an additional logarithmic communication cost. In general, our approach applies to any semi-honest linear secret-sharing based 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. Along the way, we provide a new perspective 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 can be viewed as an optimized concrete instantiation of the FLIOP-based approach. As a concrete application of our techniques, we first consider semi-honest MPC protocols based on Shamir secret sharing in the honest majority setting. Given $M$ parties and a circuit of size $N$, our approach achieves malicious security with only additional $10MN+O(M\log{N})$ total computation, logarithmic communication for reconstructing $4\log{N}+6$ secret-shared values, $O(\log{N})$ rounds, and $O(\log{N})$ correlated randomness. This demonstrates that malicious security with abort in honest majority MPC comes {\em free} in terms of both computation and communication. We then consider \emph{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 $5N+O(\log{N})$ online communication while maintaining sublinear preprocessing, less than $6N$ achieved in Le Mans (CRYPTO 2022). Our protocol leverages Sumcheck techniques to check $N$ \emph{unverified} authenticated multiplication triple relations, requiring only $N+1$ {\em standard Beaver triples} and $O(\log{N})$ random authenticated shares. Compared to the FLIOP-based verification mechanism of Boyle et al. (CRYPTO 2022), which requires $O(\sqrt{N})$ communication and $O(N^{1.5})$ computation, our approach eliminates additional cryptographic assumption beyond PCGs and achieves $O(N)$ computation.