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 unified framework for lifting semi-honest MPC protocols to maliciously secure ones, with a small {\em constant} multiplicative overhead in {\em 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$ \emph{unverified} authenticated multiplication triple relations, which requires only $N+1$ {\em 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 {\em 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.