Sum-check protocol

This article is an orphan, as no other articles link to it. Please introduce links to this page from related articles. (August 2025)

A sum-check protocol is a cryptographic protocol for the construction of interactive proof systems,^[1] used widely in zero-knowledge protocols.^[2]

The sum-check protocol was created by Carsten Lund, Lance Fortnow, Howard Karloff, and Noam Nisan and formalized in 1990.^[3][1]

In an interactive proof, the goal is for a verifier V to offload an expensive computation to an untrusted prover P.^[4] The sum-check protocol allows the prover to convince the verifier that the sum of a multivariate polynomial is equal to a known value.^[2] The goals of the sum-check protocol are to make the verifier run in time linear to the input size, to keep the proof logarithmically small, and to keep the prover efficient.^[4]

For a v-variate polynomial g defined over a finite field ${\displaystyle \mathbb {F} }$, the prover provides the verifier with the following sum:^[5]

${\displaystyle H:=\sum _{b_{1}\in \{0,1\}}\sum _{b_{2}\in \{0,1\}}\cdots \sum _{b_{v}\in \{0,1\}}g(b_{1},\ldots ,b_{v}).}$

Without a prover, the verifier has to perform ${\displaystyle 2^{n}}$ evaluations of g to verify the statement, which is a very large runtime. With the sumcheck protocol, the verifier's runtime is${\displaystyle O(v+{\text{[the cost to evaluate }}g{\text{ at a single input in }}\mathbf {F} ^{v}])}$.^[4]

The sum-check protocol leads to proofs that are of at least logarithmic length.^[4]

The protocol is not zero-knowledge by itself, and like all interactive proofs, it is not succinct for NP statements.^[4]

zk-SNARK proofs combine the sum-check protocol with commitment schemes to obtain zero-knwoledge and succinct arguments.^[4][6]

• Cryptographic protocol
• Interactive proof systems
• Zero-knowledge proof

• Thaler, Justin (July 18, 2023). "3.1, 4.1, 4.2". Proofs, Arguments, and Zero-Knowledge (PDF). Georgetown University.
• Tauman Kalai, Yael (2023). "Lecture 1: Interactive Proofs and the Sum-Check Protocol". MIT OpenCourseWare, Advanced Topics in Cryptography. Archived from the original on 20 March 2025. Retrieved 2025-08-25.