Sum-check protocol
A sum-check protocol is a cryptographic protocol for the construction of interactive proof systems,[1] used widely in zero-knowledge protocols.[2]
History
The sum-check protocol was created by Carsten Lund, Lance Fortnow, Howard Karloff, and Noam Nisan and formalized in 1990.[3][1]
Concept
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 , the prover provides the verifier with the following sum:[5]
Without a prover, the verifier has to perform evaluations of g to verify the statement, which is a very large runtime. With the sumcheck protocol, the verifier's runtime is.[4]
Limitations
Proof size
The sum-check protocol leads to proofs that are of at least logarithmic length.[4]
Zero-knowledge and succinctness
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]
See also
- Cryptographic protocol
- Interactive proof systems
- Zero-knowledge proof
References
- ↑ 1.0 1.1 Lund, Carsten; Fortnow, Lance; Karloff, Howard; Nisan, Noam (1992-10-01). "Algebraic methods for interactive proof systems" (in en). Journal of the ACM 39 (4): 859–868. doi:10.1145/146585.146605. ISSN 0004-5411. https://dl.acm.org/doi/10.1145/146585.146605.
- ↑ 2.0 2.1 "The intuition behind the sum-check protocol in 5 minutes - cryptologie.net". https://cryptologie.net/posts/the-intuition-behind-the-sum-check-protocol-in-5-minutes/.
- ↑ Lund, C.; Fortnow, L.; Karloff, H.; Nisan, N. (1990-10-01). "Algebraic methods for interactive proof systems". Proceedings [1990] 31st Annual Symposium on Foundations of Computer Science. pp. 2–10 vol.1. doi:10.1109/FSCS.1990.89518. ISBN 0-8186-2082-X.
- ↑ 4.0 4.1 4.2 4.3 4.4 4.5 Thaler, Justin (2020-03-16). "The Unreasonable Power of the Sum-CheckProtocol" (in en-US). https://zkproof.org/2020/03/16/sum-checkprotocol/.
- ↑ Thaler, Justin (July 18, 2023). "3.1, 4.1, 4.2" (in en). Proofs, Arguments, and Zero-Knowledge. Georgetown University. pp. 33. https://people.cs.georgetown.edu/jthaler/ProofsArgsAndZK.pdf.
- ↑ Bagad, Suyash; Domb, Yuval; Thaler, Justin (2024), The Sum-Check Protocol over Fields of Small Characteristic, 2024/1046, https://eprint.iacr.org/2024/1046, retrieved 2025-08-25
External links
- Thaler, Justin (July 18, 2023). "3.1, 4.1, 4.2" (in en). Proofs, Arguments, and Zero-Knowledge. Georgetown University. https://people.cs.georgetown.edu/jthaler/ProofsArgsAndZK.pdf.
- Tauman Kalai, Yael (2023). "Lecture 1: Interactive Proofs and the Sum-Check Protocol". https://ocw.mit.edu/courses/6-5630-advanced-topics-in-cryptography-fall-2023/pages/lecture-1-interactive-proofs-and-the-sum-check-protocol/.
 |  |
