Distributed Statistical Zero-Knowledge Proofs via Sumcheck

Benjamin Jauregui, Masayuki Miyamoto · 2026

Read Distributed Statistical Zero-Knowledge Proofs via Sumcheck by Benjamin Jauregui, Masayuki Miyamoto (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-14015.txt.

Introduction

Jauregui and Miyamoto build distributed statistical zero-knowledge proofs from the Sumcheck protocol. Such proofs remain scarce and mostly tied to single problems, despite rapid progress on interactive proofs. The paper defines the statistical variant, with each node's view mimicked within tiny statistical distance. It then lifts the old Sumcheck into a modular building block, yielding a distributed version that checks polynomial sum claims over a finite field.

Catalog record

CREATORBenjamin Jauregui, Masayuki Miyamoto
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE151460
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.14015

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Distributed Statistical Zero-Knowledge Proofs via Sumcheck Benjamin Jauregui, Masayuki Miyamoto Abstract We study distributed zero-knowledge proofs, introduced by Bick, Kol, and Oshman (SODA 2022). Although distributed interactive proofs (dIP) have progressed rapidly in recent years, general-purpose techniques for distributed zero-knowledge proofs remain limited and are often problem-specific. We address this gap by introducing distributed statistical zero-knowledge, requiring that each node’s view be simulatable within a negligible statistical distance, and by using this notion to lift the robust Sumcheck protocol (Lund, Fortnow, Karloff and Nisan, FOCS’90) into a modular primitive for constructing distributed zero-knowledge proofs. Our main technical contribution is a distributed zero-knowledge implementation of the Sumcheck protocol. Given oracle access to a global polynomial F F over a finite field 𝔽 \mathbb{F} with N N variables, we design a protocol to verify claims of the form ∑ x ∈ 𝔽 F ⁡ ( x ) = a \sum_{x\in\mathbb{F}}F(x)=a using O ⁡ ( N ) O\!\left(N\right) rounds of O ⁡ ( log ⁡ | 𝔽 | ) O\!\left(\log|\mathbb{F}|\right) -bit messages, while achieving the statistical zero-knowledge property and small soundness error. We then apply this primitive for two families of problems: • Non-k-Colorability : An 𝒪 ⁡ ( n ) \mathcal{O}(n) -round, 𝒪 ⁡ ( log 1 + o ⁡ ( 1 ) ⁡ n ) \mathcal{O}(\log^{1+o(1)}n) -bit distributed statistical zero-knowledge proof deciding if a graph is not k k -colorable, for any constant k k . This is the first nontrivial distributed interactive proof for this problem (even for the case k = 3 k=3 , or without zero-knowledge guarantees), with total 𝒪 ~ ​ ( n ) \tilde{\mathcal{O}}(n) per-node communication with the prover, contrasting with the Ω ~ ​ ( n 2 ) \tilde{\Omega}(n^{2}) lower bound for non-interactive proofs (Göös–Suomela, DC 2016). • Subgraph Counting : An 𝒪 ⁡ ( k ​ log ⁡ n ) \mathcal{O}(k\log n) -round, 𝒪 ⁡ ( k ​ log ⁡ n ) \mathcal{O}(k\log n) -bit distributed statistical zero-knowledge proof to count the number of induced/non-induced copies of a given k k -node pattern H H in a graph. For a superconstant k k , this is the first distributed interactive proof. For constant k k , our protocol improves the round and message complexity of the distributed interactive proof of Naor–Parter–Yogev (SODA 2020) from polylog ⁡ ( n ) \mathrm{polylog}(n) to almost 𝒪 ⁡ ( log ⁡ n ) \mathcal{O}(\log n) , while additionally providing a statistical zero-knowledge property. We note that the only previously known distributed zero-knowledge results concerning subgraph counting focus on triangle-freeness in a 1-round protocol (Grilo–Paz–Perry, 2026), which requires O ~ ​ ( n ) \tilde{O}(\sqrt{n}) -bit message per node. We further show that beyond the baseline 𝒪 ⁡ ( N ) \mathcal{O}(N) -round Sumcheck protocol, additional round compression of the Sumcheck protocol is problem-dependent. For Subgraph Counting with constant k k , a divide-and-conquer approach, recently developed for interactive oracle proofs (Levrat–Medevielle–Nardi, CiC 2025) yields a round complexity of 𝒪 ⁡ ( log ⁡ log ⁡ n ) \mathcal{O}(\log\log n) , at the cost of slightly larger per-node messages of size 𝒪 ⁡ ( log 2 + o ⁡ ( 1 ) ⁡ n ) \mathcal{O}(\log^{2+o(1)}n) per round. In contrast, for the problem Non-3-Colorability on constant-degree graphs, we obtain an 𝒪 ⁡ ( n / log ⁡ n ) \mathcal{O}(n/\log n) -round protocol and prove a conditional lower bound ruling out o ⁡ ( n / log ⁡ n ) o(n/\log n) rounds even on constant-degree graphs when each node is restricted to polynomial-time computation. 1 Introduction Interactive proofs (IP) [ 3 , 28 ] have been a key computational model studied in complexity theory since their introduction. In this model, an interactive proof (IP) is a protocol in which two parties, a prover and a verifier, engage in alternate rounds of communication to establish the validity of a statement. The prover is assumed to have unbounded computational power and aims to convince the verifier that the statement is true. The verifier is limited to efficient (typically polynomial-time) computation and uses randomness in its decisions. If the statement is true, the prover can convince the verifier with high probability, and if it is false, no matter what strategy a malicious prover follows, it will fail to convince the verifier except with small probability. One of the most famous IP is the Sumcheck protocol, introduced by Lund, Fortnow, Karloff, and Nisan [ 44 ] . This is an interactive protocol that allows the verifier to check in polynomial time an equality of the form \sum_{x\in A}F(x)=a , where F is a N -variate polynomial over a finite field, and the set A has size exponential in N (typically, a boolean hypercube \{0,1\}^{N} ). This question arose in the context of placing \#\mathsf{P} within interactive proofs. The sumcheck protocol revealed that the power of interactive proofs is far greater than originally believed, ultimately leading to Shamir’s landmark result \mathsf{IP}=\mathsf{PSPACE} [ 54 ] . Since its inception, Sumcheck has found a wide range of applications, from verifiable delegation of computation [ 27 , 52 ] to real-world blockchain systems [ 57 , 7 ] . While interactive proofs allow one to convince the verifier (with high probability) that a statement is true, they may also reveal why it is true, namely the witness or some information that may be impossible to obtain by the verifier (in polynomial time) without the help of the prover. Goldwasser, Micali, and Rackoff [ 28 ] introduced zero-knowledge proofs to study such leakage. As in any interactive proof, a powerful prover tries to convince a computationally bounded verifier of the validity of a claim through a sequence of message exchanges. What makes zero-knowledge proofs distinctive is that, even after the entire interaction, the verifier cannot gain any information that could not have been generated independently (in polynomial time), without access to the prover’s knowledge. This ensures that the prover’s “witness” or secret remains completely hidden, while still enabling the verifier to be convinced of the statement’s correctness. In this paper, we adapt the Sumcheck protocol to the distributed setting and present a distributed zero-knowledge variant of it. 1.1 Distributed verification and zero-knowledge. In recent years, interactive proofs have been extended to the distributed setting. A distributed interactive proof (dIP), introduced by Kol, Oshman, and Saxena [ 39 ] , enables the nodes of a graph G which can communicate only with their immediate neighbors, to verify a global predicate \mathcal{P} about G with the assistance of an untrusted prover. Communication proceeds in synchronous and alternating rounds between the nodes and the prover. After the interaction ends, each node executes a verification algorithm from a fixed class of distributed algorithms \mathcal{A}_{V} that determines whether it accepts or rejects. More precisely, in an r -round dIP where the prover and each node exchange \ell -bit messages in each round, the class \mathcal{A}_{V} of verification algorithms will always be a class of distributed algorithms \mathcal{C}[\mathcal{O}(1),r\ell] that run in \mathcal{O}(1) synchronous rounds, and the neighbors exchange messages of size at most \mathcal{O}(r\ell) bits on every edge in each communication round (and hence \mathcal{O}(r\ell) total communication bits per edge). In each dIP, the values r and \ell are defined according to the

Read the complete text