Conceptio › Archive › arXiv CS

arXiv CSopen access

Distributed Statistical Zero-Knowledge Proofs via Sumcheck

2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

Open Source ↗Direct PDF ↓

cloud distributed-computing parallel-computing

distributed computing, parallel computing, cloud

Distributed Statistical Zero-Knowledge Proofs via Sumcheck Benjamin Jauregui1,2 and Masayuki Miyamoto3 1

arXiv:2605.14015v1 [cs.DC] 13 May 2026

Universidad de Chile, Chile IRIF, Université Paris Cité, France 3 University of Tsukuba, Japan

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 polynomialP F over a finite field F with N variables, we design a protocol to verify claims of the form x∈F F (x) = a using O(N ) rounds of O(log |F|)-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 O(n)-round, O(log1+o(1) n)-bit distributed statistical zeroknowledge proof deciding if a graph is not k-colorable, for any constant k. This is the first nontrivial distributed interactive proof for this problem (even for the case k = 3, or without zero-knowledge guarantees), with total Õ(n) per-node communication with the prover, contrasting with the Ω̃(n2 ) lower bound for non-interactive proofs (Göös– Suomela, DC 2016). • Subgraph Counting: An O(k log n)-round, O(k log n)-bit distributed statistical zeroknowledge proof to count the number of induced/non-induced copies of a given k-node pattern H in a graph. For a superconstant k, this is the first distributed interactive proof. For constant k, our protocol improves the round and message complexity of the distributed interactive proof of Naor–Parter–Yogev (SODA 2020) from polylog(n) to almost 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)-bit message per node. We further show that beyond the baseline O(N )-round Sumcheck protocol, additional round compression of the Sumcheck protocol is problem-dependent. For Subgraph Counting with constant k, a divide-and-conquer approach, recently developed for interactive oracle proofs (Levrat–Medevielle–Nardi, CiC 2025) yields a round complexity of O(log log n), at the cost of slightly larger per-node messages of size O(log2+o(1) n) per round. In contrast, for the problem Non-3-Colorability on constant-degree graphs, we obtain an O(n/ log n)-round protocol and prove a conditional lower bound ruling out o(n/ log n) rounds even on constantdegree graphs when each node is restricted to polynomial-time computation.

Contents 1 Introduction 1.1 Distributed verification and zero-knowledge. . . . . . . . . . . . . . . . . . . . . . 1.2 Our contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Overview of our techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4 Other related work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3 3 5 8 13

2 Preliminaries. 2.1 Distributed interactive proofs and distributed zero-knowledge proofs . . . . . . . 2.1.1 Zero-knowledge property . . . . . . . . . . . . . . . . . . . . . . . . . . . .

14 15 16

3 Sumcheck Protocol: General Framework. 3.1 The Distributed Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 General Toolbox for the zero-knowledge simulation. . . . . . . . . . . . . . . . . . 3.2.1 Zero-knowledge implementation of Step 1. . . . . . . . . . . . . . . . . . . 3.3 Zero-knowledge implementation of Step 2. . . . . . . . . . . . . . . . . . . . . . . 3.4 Zero-knowledge implementation of Step 3 and final application. . . . . . . . . . . 3.5 Final protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.6 Completeness and Soundness . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

17 18 20 21 24 25 25 30

4 Applications of Distributed Sumcheck 4.1 Non-k-Colorability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Counting Subgraphs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

31 31 36

5 Reducing Round Complexity by Divide-and-Conquer Sumcheck 5.1 Splitting the instance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Proof of Theorem 12 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

40 41 43

6 A Barrier for Round Reduction for Non-k-Colorability 6.1 Upper Bound for Constant-Degree Graphs . . . . . . . . . . . . . . . . . . . . . . 6.2 Conditional Lower Bound for Constant-Degree Graphs . . . . . . . . . . . . . . .

44 44 44

7 Conclusion

Introduction

Interactive proofs (IP) [Bab85, GMR89] 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 [LFKN92]. This is an interactive protocol that allows the P verifier to check in polynomial time an equality of the form F x∈A (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 #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 IP = PSPACE [Sha92]. Since its inception, Sumcheck has found a wide range of applications, from verifiable delegation of computation [GKR15, RRR16] to real-world blockchain systems [XZZ+ 19, BSCR+ 19]. 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 [GMR89] 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 [KOS18], enables the nodes of a graph G which can communicate only with their immediate neighbors, to verify a global predicate 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 AV that determines whether it accepts or rejects. More precisely, in an r-round dIP where the prover and each node exchange ℓ-bit messages in each round, the class AV of verification algorithms will always be a class of distributed algorithms C[O(1), rℓ] that run in O(1) synchronous rounds, and the neighbors exchange messages of size at most O(rℓ) bits on every edge in each communication round (and hence O(rℓ) total communication bits per edge). In each dIP, the values r and ℓ are defined according to the problem. (see Section 2.1 for the formal definition). A dIP Π is said to be valid for P if it satisfies the standard completeness and soundness conditions. Completeness requires that if G satisfies P, then there exists an assignment of messages given by the prover to the nodes, such that with high probability all nodes accept. Soundness requires that if G does 3

not satisfy P, then regardless of the prover’s strategy, with high probability at least one node rejects. The model generalizes classical proof-labeling schemes (PLS) [KKP10] and locally checkable proofs (LCP) [GS16], which correspond to the special case of a single, non-interactive round. The class AV of verification algorithms is limited to 1-round broadcast CONGEST algorithms where the broadcast message is always its own proof for PLSs, and is C[O(1), ∞] (i.e., constant round LOCAL algorithms) for LCPs. See also Section 1.4 for related work. Zero-knowledge in dIP. The core intuition behind (the centralized definition) of zeroknowledge is that, on yes-instances, anything that a probabilistic polynomial-time verifier learns from the interaction could already be produced, without interacting with the prover, by a probabilistic polynomial-time simulator. More formally, the (perfect) zero-knowledge property of an IP Π requires that for every verifier in the class of probabilistic polynomial time algorithms Apoly , there exists an algorithm A ∈ Apoly , called a simulator, that samples the verifier’s full view with the exact distribution of a real execution of Π. In contrast to the centralized setting, in distributed models, an efficient algorithm is typically considered a local algorithm (ideally, a constant-round distributed algorithm), i.e., anything the nodes exchange with their constant-hop neighbors is deemed legal. With this in mind, Bick, Kol, and Oshman [BKO22] defined the notion of distributed zero-knowledge (dZK) proofs: informally, given a (sub)class of constant-round distributed algorithms Aconst , a distributed interactive protocol satisfies the zero-knowledge property with respect to the class Aconst if for every yes-instance there exists a distributed algorithm from Aconst , a.k.a. a simulator, whose local output in each node is identical (in distribution) to the real transcript that each node has after the execution of the dIP (see Section 2.1 for formal definition). In [BKO22] the authors provided a three-round dZK protocol for 3-Colorability using O(deg(v))-bit message per node and an one-round dZK for Spanning Tree Verification using O(log n)-bit message per node, both having a simulator from the class C[1, O(log n)]. Recently, Grilo, Paz, and Perry [GPP25] showed one-round dZK protocols for 3-Colorability using O(log n)-bit message √ per node and for triangle-freeness using Õ( n)-bit message per node, with a simulator from the √ class C[1, O(log n)] and C[1, Õ( n)], respectively. As more general results, (1) [BKO22] provided a compiler that transforms a proof-labeling scheme (PLS) to a dIP protocol that satisfies the distributed zero-knowledge property defined in [BKO22], where the simulator class depends on the parameters of the PLS. In particular, the dIP that satisfies the zero-knowledge property significantly increases the proof size, and (2) [GPP25] showed how to certify any graph property in NP, which is zero-knowledge under some cryptographic assumptions (such as the existence of one-way functions). Despite the progress, two conceptual gaps remain: Generality. Existing dZK protocols have some drawbacks: problem-specific, inefficient, or dependent on cryptographic assumptions. There is no general primitive akin to sumcheck that automatically yields efficient protocols that are unconditionally zero-knowledge, applicable for a wider class of properties. Perfect vs statistical ZK. The zero-knowledge property defined in [BKO22] emulates the perfect zero-knowledge property in IP protocols, where the simulator algorithm needs to simulate exactly the view (as distribution) that the ZK protocol. While this definition is the main goal that we should ask for a zero-knowledge proof algorithm, it is known in IP protocols that is now known to be achievable for all problems. In classical cryptography and complexity theory, relaxing to statistical zero-knowledge, where we ask the simulator

to generate a close enough view of the original view of the protocol (see Section 2.1 for a formal definition), unlocks simpler and more modular constructions. Such a relaxation has not been explored in the distributed setting.

1.2

Our contributions

We move beyond previous limitations by lifting the classical sumcheck protocol [LFKN92] to the distributed domain. In this framework, we study tuples of the form (G, F, q, a) where G is an n-node communication graph of the distributed verifier with unique identifiers from the range {0, . . . , n − 1}, F : FN q → Fq is an N -variable polynomial of total degree d, q is a prime number representing the size of a finite field Fq , and a ∈ Fq is the claimed target value, where the goal P is to decide if x∈Fq F (x) = a. We call such a tuple a Sumcheck-instance; and in any given Sumcheck-instance (G, F, q, a), each node receives q, a as input and has oracle access to F . While it is not hard to obtain a distributed implementation of Sumcheck protocol through classical techniques such as aggregations over a spanning tree, we move directly to study how to obtain a distributed implementation of Sumcheck protocol that satisfies a zero-knowledge property. Specifically, we consider the following input: each node has oracle access to F , and the input to each node includes q, a, and by simplicity we also assume the each node receives the ID of the parent in a rooted spanning tree with the ID of the root node is 0. See Remark 1. Theorem 1 (Distributed ZK Sumcheck). There exists a statistical zero-knowledge distributed interactive proof such that, for any Sumcheck-instance (G, F, q, a), where F is an N -variable polynomial of individual degree d over a finite field Fq and any fixed parameter t ∈ N, such that the following holds: • Completeness. If • Soundness. If

x∈{0,1}N F (x) = a, then all nodes accept with probability 1.

x∈{0,1}N F (x) ̸= a, then all nodes accept with probability at most

1 Nd q + t.

The protocol runs for O(N ) rounds, with each round requiring O(log q) bits of message between the prover and each node. Moreover, the verification algorithm and the simulator belongs to the class C[O(1), O(N log q)] requiring a single oracle query to F . Remark 1 (Oracle access ⇔ aggregation tree). Throughout this work, and as usual in the dIP literature, the target polynomial F is an encoding of some global information of the graph. Usually, each node v can locally evaluate the portion Fv (x1 , . . . , xN ) of F that depends on its private information. In order to evaluate the global value F (x1 , . . . , xN ), the network needs to aggregate1 these partial evaluations along some overlay, which is in practice a rooted spanning tree. Thus, oracle access to F implicitly assumes a rooted spanning tree. Our protocol merely makes this implicit tree explicit. Even if we consider the case where the ID of parents are sent from the prover, verifying its correctness can be done with perfect zero-knowledge [BKO22]. Throughout the paper we assume the given tree T is rooted at the node with its ID 0, which is written in the input label of each node. From Theorem 1, we obtain interesting applications that surpass the state-of-the-art results. 1

This aggregation typically is an addition or multiplication of the local portion of F (x1 , . . . , xN ) computed by each node

Non-k-Colorability The first concrete problem consists of verifying if the graph is not kcolorable, for a fixed integer k, which we call Non-k-Colorability problem. Theorem 1 yields the following result. To keep the notation simple for the moment, we present an informal version of the result. A precise definition of the statistical zero-knowledge dIP class is deferred to Section 2.1, while a fully formal statement can be found in Theorem 8. Theorem 2 (Informal version of Theorem 8). Let q ∈ nω(1) be an arbitrary prime. There exists a statistical zero-knowledge dIP Π for Non-k-Colorability that requires O(n) rounds and O(log q) message size, and admits a simulator S ∈ C[O(1), O(n log q)] whose output induces, for each node, a distribution statistically close to its view in Π. Deciding even if a graph is not 3-colorable is known to be hard in locally checkable proof (i.e., one-round distributed verification): Göös and Suomela [GS16] showed that any LCP for Non-3-Colorability requires Ω(n2 / log n)-bit proof per node. Notably, while most of other known graph properties that require Ω̃(n2 ) bits in LCPs already admit efficient interactive proofs (symmetric graphs [KOS18], asymmetric graphs [NPY20], and graph nonisomorphism [NPY20]), there is no interactive proofs for Non-3-Colorability that improves the O(n2 )-bit trivial LCP (giving the adjacency matrix of the graph to each node). Our result improves the total message size per node to almost O(n log n). This is also the first zero-knowledge dIP for Non-k-Colorability. Subgraph-counting. The second problem that we study is subgraph-counting(H). In this problem, we want to verify that the number of a given k-node pattern graph H in the network is exactly ∆, which is given as the input. Using Theorem 1, we obtain the following. Theorem 3 (Informal version of Theorem 11). Let (H, ∆) be information known to all nodes, where H is a k-node graph and ∆ is a natural number (the claimed number of copies of G in the graph). Let q be a prime satisfying q ∈ nω(1) if k ∈ O(1), and q > nk if k ∈ ω(1). There exists a statistical zero-knowledge dIP Π for subgraph-counting(H) that requires O(k log n) rounds and O(log q) message size, and admits a simulator S ∈ C[O(1), O(k log q log n)] whose output induces, for each node, a distribution statistically close to its view in Π. For subgraph-counting(H), our dZK proof improves the total message size per node from [GPP25], where they showed that triangle-freeness admits an one-round dZK proof with √ √ O( n)-bit proof against a simulator from C[1, O( n)]. Note that triangle-freeness can be solved in 1-round if we allow O(n)-bit message, i.e., algorithms from C[1, O(n)]. Theorem 3 improves the result of [NPY20]. In their work, the distributed implementation of the celebrated GKR protocol [GKR15] is presented. Here, the GKR protocol is a generalpurpose interactive proof that enables a verifier to check the correctness of the output of a logspace uniform circuit in quasilinear time. More precisely, they showed that any graph property verifiable by a log-space uniform circuit of size T = poly(n) and depth d = O(log n) admits a distributed interactive proof using O(d · log T · polylog(n)) rounds and message size. Since the naive algorithm for subgraph-counting (checking all k-tuples of a graph in O(nk ) time) is implemented by a log-space uniform boolean circuit of size T = poly(n) and depth d = O(log n) when k ∈ O(1), it admits a distributed interactive proof of polylog(n) round and message complexity. Intuitively, the GKR protocol utilizes the sumcheck protocol O(d) times, resulting in an O(d) multiplicative factor in the round/message complexity. Therefore, their compiler can be regarded as a black-box implementation of sumcheck. We “open this black-box”, and apply our sumcheck compiler directly, rather than through a black-box GKR layer, to the polynomial encoding the number of subgraphs, in order to bypass the depth-d overhead of the GKR protocol. 6

More importantly, our result is applicable for the k ∈ ω(1) regime, where subgraph-counting does not seem accessible through the distributed GKR protocol of [NPY20]. 2 Optimizing round complexity of subgraph-counting(H). From the first distributed implementation of Sumcheck given by Theorem 1, we manage to improve the round complexity using a divide-and-conquer technique inspired from [LMN25]: Theorem 4 (O(log log n)-round protocol for subgraph-counting(H)). Let (H, ∆) be information known to all nodes, where H is a k-node graph and ∆ is a natural number (the claimed number of copies of G in the graph). Let q be a prime satisfying q ∈ nω(1) if k ∈ O(1), and q > nk if k ∈ ω(1). There exists a statistical zero-knowledge dIP Π for subgraph-counting(H) that 2 log q requires O(k log k + log log n) rounds and O log k + k log k log q message size, such that the view of each node after the execution of S has a distribution statistically close to the distribution of the view of each node in Π. Notably, for k ∈ O(1), this gives exponentially small round complexity of O(log log n) with slightly increased message size of O(log2+o(1) n). Conditionally optimal round complexity for Non-k-Colorability So far we have seen that the polynomial specially designed for subgraph-counting(H) admits an exponential round compression, i.e., from the naive O(log n) to O(log log n). This raises the following natural question: Can the O(n) rounds in our Non-k-Colorability protocol be improved—perhaps to polylogarithmic complexity? We show that for constant-degree graphs, the round complexity can be reduced to O(n/ log n), which is essentially optimal under some realistic setting, showing that substantial further reductions are unlikely. Theorem 5. There is a statistical zero-knowledge dIP protocol for Non-k-Colorability on constant-degree graphs that uses O(n/ log n) rounds and O(log2 n) bits per node per round. In contrast, assume UNSAT ∈ / AMTIME[2o(n) ] and let Π be any dIP protocol for Non-3-Colorability in which each node is a polynomial-time Turing machine. Then Π must use Ω logn n rounds even for constant-degree graphs. Here, we condition on the assumption that any two-round Arthur-Merlin protocol with a subexponential-time verifier cannot decide the unsatisfiability of a given formula. This is sometimes called “Arthur-Merlin ETH”, which has been mentioned by several papers [GVW02, CGI+ 16, Wil16, BGK+ 25]3 . Consequently, our O(n/ log n)-round protocol is optimal unless (1) major breakthroughs occur in Arthur–Merlin complexity, or (2) the verification algorithm uses exponential-time like in the trivial Ω(n2 )-bit PLS using the adjacency matrix4 . On the other hand, Theorem 5 also exhibits that there is not much room in reducing total per-node message complexity of this problem: the trivial PLS (sending all edges in the graph to each node) requires Ω(n)-bit per node for constant-degree graphs, while Ω(n2 / log n)-bit are required even on the interactive setting. 2 The problem of detecting a k-clique, a special case of subgraph-counting, is a canonical W[1]-hard problem (i.e., one for which no poly-time algorithm is believed to exist). Moreover, even no(k) -time algorithm violates the exponential-time hypothesis [CFK+ 15]. 3 Note that even a faster than 2n two-round AM protocol would still be a big achievement [BGK+ 25]. 4 In the trivial O(n2 )-bit PLS, each node receives the entire topology of the graph as the adjacency matrix, and then decides its local output by solving Non-3-Colorability (a coNP-hard problem) in exponential time.

1.3

Overview of our techniques

We now outline the technical ingredients that drive our results. First of all, in all of our protocols we assume that each node knows the ID of its parent in an arbitrary spanning tree (and for simplicity assume that the root node has ID 0). This is safe, since the spanning tree can be verified using additional O(log n)-bit in the proofs of the first round by using the classical result of [KKP10] (for non-zero-knowledge protocols) or the dZK proof of [BKO22]. dIP for Sumcheck Protocol. tocol [LFKN92] (Protocol 1.1).

The starting point is the Lund–Fortnow–Karloff–Nisan pro-

Protocol 1.1: Sumcheck-Protocol N Input: A polynomial P F : F → F, and a field element a ∈ F. Goal: Check that x∈{0,1}N F (x) = a.

1. Step 1. • The prover sends an univariate polynomial g1 (x1 ). • The verifier checks g1 (0) + g1 (1) = a, rejects otherwise. 2. Step 2. Repeat the following for 2 ≤ i ≤ N : • The verifier picks ri−1 ∈ F u.a.r., sends to the prover. • The prover sends an univariate polynomial gi (xi ). • The verifier checks gi (0) + gi (1) = gi−1 (ri−1 ), rejects otherwise. 3. Final Check: The verifier picks rN ∈R F, checks gN (rN ) = F (r1 , . . . , rN ), rejects otherwise. In this protocol, during each prover’s turn i ∈ {1, . . . , N }, the prover provides an univariate polynomial gi , where N is the number of variables in the original polynomial. In our distributed implementation, each polynomial gi is represented by n coefficients, i.e., gi (x) =

n−1 X

αj xj ,

j=0

with each coefficient αj stored at a distinct node. A distributed implementation (without zero knowledge guarantees) of the Sumcheck protocol follows essentially from the scheme described in Protocol 1.1. Concretely, each evaluation of gi is carried out by a converge-cast along a spanning tree, which aggregates the coefficient-weighted monomials given by the prover, and finally the root of the spanning tree is in charge to verify the respective equality in each step. This requires only one round of assistance from the prover: the coefficients are assigned to nodes through the spanning tree, enabling the root to verify the resulting equality. This construction yields the naı̈ve distributed implementation of the Sumcheck protocol (see Section 3 for details). Zero-knowledge framework. The naı̈ve implementation described above reveals coefficients of polynomials, hence each node learns rich structural data. Zero-knowledge therefore, requires hiding all intermediate polynomials. For example, consider the task of computing the simple arithmetic sum of n private inputs: each node v ∈ {0, . . . , n − 1} holds a private bit bv ∈ {0, 1}, 8

P this in the sumcheck form we take and let a = nv=1 bv be the value we want to verify. To phraseP the N = log n-variate multilinear extension F (x1 , . . . , xN ) = n−1 v=0 bv · χv (x1 , . . . , xN ) where χv is the standard indicator polynomial for the binary representation of v. The sumcheck protocol P applies to check x∈{0,1}log n F (x) = a. Under the distributed implementation described above, the root of the spanning tree performing the convergecast verifies all equalities with high probability. In particular, the root will learn the values g1 (0) and g1 (1) of Step 1, but by definition of Sumcheck protocol , it holds that X

g1 (0) =

(x2 ,...,xN )∈{0,1}N −1

g1 (1) =

(x2 ,...,xN

F (0, x2 , . . . , xN ) =

bv · χv (0, . . . , xN )

(x2 ,...,xN )∈{0,1}N −1

F (1, x2 , . . . , xN ) =

)∈{0,1}N −1

(x2 ,...,xN

bv · χv (1, . . . , xN )

)∈{0,1}N −1

In particular, in our function F (x), the variable x1 denotes the first bit of the binary representation, and therefore g1 (1) =

X (x2 ,...,xN

bv · χv (1, . . . , xN )

)∈{0,1}N −1

v:the first bit of v is 1

= “the number of nodes with IDs ≥ n/2 whose bit value bv is 1”. Thus, the single value g1 (1) already reveals the aggregate state of half of the network, which may be located at distance Θ(n) from the root, and hence leaks information beyond the reach of constant-round simulators. Therefore, we need to modify the above approach into one that hides all the coefficients. To this end, we use several ideas from distributed and cryptographic algorithms. P In the distributed implementation described in Section 3, the verification of the equality x∈{0,1}N F (x) = a is reduced to verify O(N ) equalities: The equality g1 (0) + g1 (1) = a in Step 1 of Protocol 1.1, and N − 1 equalities gi (0) + gi (1) = gi−1 (ri−1 ) in each repetition of Step 2. While the verification of equalities has been previously studied in distributed implementations of zero-knowledge proofs (such as the verification of a spanning tree in [BKO22]) using the standard random mask approach, where the authors show how the values involved in a single equality can remain hidden from the nodes while still allowing them to verify the equality, we address a more complex scenario. In our case, each coefficient participates in multiple equalities, making the verification process more intricate. To illustrate our approach, suppose the nodes of a graph need to verify gi (0) + gi (1) = gi−1 (ri−1 ). Let us now focus on evaluating gi (1) where gi is an univariate polynomial of degree n − 1. An easy protocol could be to ask the prover to provide a single coefficient of gi to each node v in G, and let the network sum them along the spanning tree to compute gi (1) in the equality. But we want to keep the coefficients hidden from the nodes. In this new scenario, we can use randomness in order to verify the equalities without revealing the values of the addition. Instead of directly evaluating gi , you can ask the prover to send evaluations disturbed by a random uniform value, namely, to send αv + rv for each v, where αv is a coefficient of some 9

monomial in gi , and rv is an uniform random value over a field Fq . In this new set up, the nodes now can compute gi (1) if and only if X

rv = 0.

(1)

The problem is that the nodes should not be able to verify whether Equation 1 holds, as the direct verification by seeing the masks themselves could leak information about the coefficients: knowing the masked value αv + rv , and the random mask rv would reveal the coefficient αv . Therefore, instead of just asking the prover for a masked evaluation, we ask the prover to commit t different possible random masks rv1 , . . . , rvt using Shamir’s secret sharing technique, where t is a fixed security parameter. Once the prover has committed to these t values, the nodes randomly choose one index to keep hidden and open the remaining t − 1 masks. They then check that Equation (1) holds for each revealed mask, catching any cheating prover with probability at least 1 − 1/t. This strategy presents several challenges to address. For example, the prover must commit to the random values in such a way that no individual node can recover them without exchanging information with its neighbors—otherwise, a node could compute each random value committed by the prover on its own. Moreover, the nodes must ensure that if they want to verify another equality involving the same polynomial gi , then the prover is required to provide a consistent commitment for its coefficient. We address all these issues in Section 3.2, and the solutions of these problems represent some of the most technical part of our zero-knowledge implementation. To summarize, the high-level idea behind our zero-knowledge implementation is to send each node the original value masked with a random value, in such a way that all the randomness involved in the equality cancels out (i.e., their sum equals zero). This is formalized through ^ , and (0C) described in Section 3.2.1.1. The goal is to ensure the conditions (RC) , (RC) i

that these conditions hold without revealing the exact value of any random mask used, while guaranteeing that the same random value is applied consistently to each original value across all equalities in which it appears. In the applications to Non-k-Colorability and subgraph-counting(H), we need to replace oracle queries, which is not allowed in these problems, by something else. Intuitively, the random evaluations of the polynomials in the verification algorithm can be done using oneround help of the prover. In our simulators, this evaluation is replaced by an uniformly random value, which is sufficient for our purposes, as we prove that, given an uniformly random input, the distributions of the target polynomials are statistically close to the uniform distribution. For the polynomial PG in Non-3-Colorability, the evaluation is essentially close to the product of uniform random variables, which itself follows a distribution that is statistically close to the uniform distribution. For the polynomial f in subgraph-counting(H), we can use the fact that f is a multilinear polynomial, for which we show that the distribution is almost uniform. Moreover, since the masks used for our statistical zero-knowledge protocols are component-wise, each oracle call to the intermediate polynomials used in our O(log log n)-round dIP protocol for subgraph-counting(H) does not leak any information other than its evaluation value. Using the fact that every intermediate polynomial is also multilinear, we also get a statistical zero-knowledge variant of our O(log log n)-round dIP. Non-k-Colorability. We exemplify our techniques for the Non-3-Colorability problem, since its generation to Non-k-Colorability follows naturally. To instantiate our framework, given an instance (G = (V, E), I), where G is the communication graph which we want to verify if it is non-3-colorable and I denotes the input label

to each node such as the IDs of itself and its parent in a spanning tree, we use a polynomial PG : {0, 1}3n → N of 3n variables, such that for each node v ∈ V the polynomial PG has three variables rv , bv and gv , and the polynomial PG (x) = T (x) · S(x) is defined as follows. First,T is defined as follows. For each edge e = (u, v) ∈ E with u < v, define Wered := 1 − ru rv ,

Wegreen := 1 − gu gv ,

Weblue := 1 − bu bv .

Q Then, be defining Tred := e∈E Wered , and Tgreen , Tblue analogously, we define T := Tred Tgreen Tblue . On the other hand, for each node v ∈ V , define Av := 1 − (1 − rv )(1 − gv )(1 − bv ), Bv := (1 − rv gv )(1 − gv bv )(1 − rv bv ). Q And then S := v∈V Av Bv . Our polynomial construction builds on the classical reduction of 3-Coloring to 3-SAT: the resulting polynomial is the arithmetization of the reduced 3-CNF formula. Intuitively, the factor T enforces edge-consistency of the coloring, while S guarantees that each node is assigned a unique color. The sum of the constructed target polynomial P then encodes the number of valid 3-colorings. Consequently, the underlying graph is non-3-colorable if and only if the following equality holds: X PG (x) = 0. (2) x∈{0,1}3n

That is, verifying that the sum of PG over all assignments x ∈ {0, 1}3n equals zero proves that the graph is non-3-colorable. Therefore, the Sumcheck protocol from Theorem 1 reduces the verification of Non-3-Colorabilityof the input graph to deciding whether the Sumcheck-instance (G, PG , poly(n), 0) satisfies Equation (2). The evaluation of PG at a single point is performed through a spanning tree, using partial evaluations provided by the prover in a single round. Moving from Non-3-Colorability to Non-k-Colorability for any fixed integer k follows naturally: We reproduce the same reduction to obtain the polynomial PG (x) as described above, but now this polynomial has k · n variables, and the rest of the protocol proceeds in the same way. A central technical challenge in our application of the Sumcheck protocol is that the size N of the sum may be exponential in the number of nodes of the graph. Indeed, even in simple instances, the number of valid K-colorings can grow exponentially with the size of the graph; for example, a path on n nodes admits at least 3 · 2n−1 distinct 3-colorings. Consequently, the value handled by the protocol cannot, in general, be represented explicitly using a polynomial number of bits. However, in our setting, the protocol requires that every intermediate value communicated between nodes be encoded using only O(log n) bits, independently of the prover’s strategy. To achieve this, we rely on the Prime Number Theorem and perform the computation modulo a suitably chosen prime q. This allows all intermediate quantities to remain logarithmic in size. Moreover, by selecting q from an appropriate range, we ensure that, with high probability, the protocol still correctly certifies the property, since distinct values collide modulo q only with negligible probability. Subgraph-Counting. For subgraph-counting(H), we describe the high-level idea for the case of triangles. Triangle counting is a well-studied problem in the centralized setting. Given

a graph G, the number of triangles of G, denoted as #∆(G), can be obtained by matrix multiplication: 1 #∆(G) = tr(A3 ), 6 where tr is the trace of a matrix and A is the adjacency matrix of the graph G. To rephrase this relation by a sum of a polynomial, the adjacency matrix A is viewed as a boolean function, then e over a large field. Now we get a polynomial it is extended to a unique multilinear polynomial A e A of 2⌈log n⌉ variables. The final polynomial f is defined as e j) · A(j, e k) · A(k, e i), f (i, j, k) = A(i, which is a 3⌈log n⌉-variate polynomial of individual degree 2. By known facts about multilinear X f (i, j, k) is equal to tr(A3 ), and therefore we extensions, it is known that the sum i,j,k∈{0,1}log n

can use the Sumcheck protocol P to compute the number of triangles. Now our Sumcheck compiler reduces the computation of i,j,k f (i, j, k) to a single evaluation of f , using O(log n)-rounds of interaction. Later in our zero-knowledge simulator, we check that the evaluation can be replaced by an uniform random value, as an evaluation on a random point is nearly uniform. Reducing the round complexity of Sumcheck for triangle counting. In the above triangle counting protocol, the number of triangles is encoded in the sum of a O(log n)-variate polynomial. During each round of the Sumcheck, the intermediate univariate polynomial has O(log n) monomials, and oracle access to it is realized by distributing the coefficients of monomials over the network. During each oracle call, the other nodes sit idle, wasting parallel bandwidth of the network. We remedy this by inflating the intermediate polynomial: borrowing the idea of [LMN25], we eliminate a constant ratio of variables in each round, instead of a single variable as in the standard Sumcheck. The idea of [LMN25] is summarized as follows. In the original Sumcheck protocol, at each round 2 ≤ i ≤ N , the protocol considers the Sumcheck relation P ai = gi over N − i + 1 variables, where X ai := F (r1 , . . . , ri−1 , xi , . . . , xN ) xi ,...,xN ∈{0,1}

is implicitly given as a polynomial gi−1 whose correctness verified by the previous rounds (together with the final check). Therefore, each round is typically viewed as eliminating a single variable by replacing it with a random value. Instead, P we eliminate N/2 variables P ′in a single ′ round, reducing the original Sumcheck relation a = F to a new relation a = F , where X F ′ (·) = F (·, xN/2+1 , . . . , xN ) xN/2+1,...,xN ∈{0,1}

has N/2 variables, and a′ is defined by a′ = a. In this case, the sum remains the same and we don’t need to verify its correctness. Instead, we need to verify the correctness of a given polynomial F ′ . To this end, we define another polynomial F ′′ of N/2 variables F ′′ (·) = F (r1 , . . . , rN/2 , ·) P ′′ for random values r1 , . . . , rN/2 and introduce another Sumcheck relation a′′ = F where a′′ = F ′ (r1 , . . . , rN/2 ) that binds F ′ . To summarize, with a single round, the original Sumcheck instance is reduced to two Sumcheck instances of polynomials of N/2 variables. 12

Actually, this protocol does not work as is since we cannot implement oracle access to these polynomials in our setting. We carefully choose the number of variables eliminated in each round so that the polynomial corresponding F ′ above has exactly n coefficients. Each coefficient is then mapped to a unique node, giving the network oracle access to the polynomial that fully exploits parallel bandwidth of the network. The same variable elimination procedure is repeated recursively for F ′ , until we reach single-variable polynomials. The implementation of this idea finally gives Theorem 4. One caveat of this approach is that each elimination doubles the number of polynomials to be Sumchecked. It can be overcome by the folding technique of [LMN25], which enables us to fold multiple instances of Sumcheck into a single Sumcheck. Crucially, the number of monomials in the intermediate polynomials in the whole procedure does not exceed n, so oracle access to these polynomials can be realized by short certificates. Round complexity of Non-k-Colorability on constant-degree graphs. We now turn back to the polynomial T ·S for Non-k-Colorability. Each variable of the polynomial appears in T at most as many as k times the degree of the corresponding node. Focusing on constantdegree graphs makes the individual degree of the polynomial O(1). Here, we P use the same idea for triangle counting. In each repetition, we reduce F for N -variate P the Sumcheck P erelation a = polynomial into two Sumcheck relations a′ = h and a′′ = h, where h is a O(log n)-variate polynomial which is the sum of F over the sub-hypercube on all variables except the first O(log n) variables. This polynomial can be specified by O(n) monomials, as the individual degree of F is O(1). In particular, oracle access to h is achieved by distributing the coefficients. Another polynomial e h consists of exponentially many monomials, and we repeat the same procedure for Pe the Sumcheck relation a′′ = h to eliminate O(log n) variables at once. Eventually, we get O(n/ log n) instances of Sumcheck each concerning an O(log n)-variable polynomial. The whole procedure to generate these instances requires O(n/ log n)-round, and O(log2 n)-bit of messages. To solve these instances in O(n/ log n) rounds, we process O(log n) instances at once in parallel using the standard Sumcheck, as we can use O(log2 n)-bit of messages. To solve all instances, we need to repeat this for O(n/ log2 n) times sequentially, each requiring O(log n) rounds. Finally, to achieve a barrier to lower-round complexity, we leverage the reduction from 3SAT to 3-coloring. (Note that the direction of reduction is opposite to the reduction used to obtain the polynomial for this problem.) Starting from an instance of 3-SAT, it is first reduced to 2o(n) many sparse formulas using the sparsification lemma [IPZ01]. Each sparse instance is converted to an instance of 3-coloring, and due to the sparsity, the converted graph has a constant maximum degree. Now, assuming that each node is a polynomial-time Turing machine, it is not difficult to simulate a distributed interactive proof in the centralized setting using the same number of rounds. Finally, the round reduction technique [GVW02] applied to the simulated interactive proof yields a subexponential-time Arthur-Merlin protocol to solve unsatisfiability of the original instance, which obviously breaks the Arthur-Merlin Exponential-Time Hypothesis.

1.4

Other related work

Recently in [MMRW25, JMMRW26] it was defined the notion of hiding locally checkable proofs, which is reminiscent of zero-knowledge proofs. They constructed hiding LCPs of k-coloring, that is, LCPs that certify k-COLORABILITY while hiding the actual colors in the sense that no constant-round distributed algorithm can recover the k-coloring from the provided proofs. This is different from dZK proofs; for 2-coloring, giving a valid 2-coloring reveals nothing new, so it is a dZK proof, but is not a hiding LCP.

A series of papers has studied efficient protocols in the dIP model [MRRR21, JMR22, GP25, GP26]. Several trade-off results such as space vs. communication or shared vs. private randomness are explored by [CFP19]. The role of shared randomness is also studied in [MRRR25]. In [LGMN23b], the quantum variant of dIP is introduced, extending the framework of noninteractive quantum proofs [FLGNP21, LGMN23a, HKN24]. Distributed verification itself was first introduced by Ref. [KKP10]. Its variants [FPSP19, FMO+ 19, CHPP20, GS16] have been studied as well. Zero-knowledge implementations of Sumcheck have been considered in the centralized IPs [CFS17, BSCF+ 17, CFGS22, GOS24, GOS25]. These results achieve perfect zero-knowledge, but focus on other models such as (interactive) PCPs or multi-prover IPs, instead of IPs. In the IP model, while Sumcheck can be made computational zero-knowledge assuming the existence of one-way functions [BOGG+ 90], achieving statistical zero-knowledge for Sumcheck would imply complexity-theoretic collapses [For87]. Distributed algorithms concerning security against adversaries have been considered in several settings [HPY23, HP21, FP23, PY19a, PY19b]. Additionally, [ATO24, ATBC+ 23] studied efficient verification of distributed CONGEST algorithms with a computationally limited prover.

Preliminaries.

An undirected graph G = (V, E) consists of a finite set V of nodes and a set E ⊆ V2 of unordered pairs of distinct nodes, called edges. Throughout the paper, we let n := |V |. A path in G is a sequence of nodes v0 , v1 , . . . , vk such that {vi−1 , vi } ∈ E for all i ∈ {1, . . . , k}. The length of the path is k. The distance between two nodes u, v ∈ V , denoted distG (u, v), is the minimum length of a path connecting u and v, if such a path exists. The graph G is connected if for every pair of nodes u, v ∈ V , there exists a path connecting ′ u and v. A subgraph of G is a graph G′ = (V ′ , E ′ ) such that V ′ ⊆ V and E ′ ⊆ E ∩ V2 . If V ′ = V , then G′ is called a spanning subgraph of G. A tree is a connected graph with no cycles. A spanning tree of a connected graph G is a subgraph T = (V, ET ) that is a tree and satisfies ET ⊆ E. For a node v ∈ V , we denote by N (v) := {u ∈ V | {u, v} ∈ E} the set of neighbors of v, and by deg(v) := |N (v)| its degree. The maximum degree of G is denoted by ∆(G) := maxv∈V deg(v). For an integer m, we use [m] := {1, . . . , m}. Given a prime q, we denote as Fq = {0, 1, . . . , q − 1} the finite field of order q (with addition and multiplication taken modulo q). We denote its multiplicative group by F× q = Fq \ {0}. For any finite set Ω, we write X ∼ Unif(Ω) to mean that X is drawn uniformly at random from Ω, or simply X ∈R Ω. Given two measures µ and ν on a measurable space (Ω, F ), the total variation distance TV (µ, ν) is defined as follows. Definition 1 (Total Variation Distance). Given a measure space (Ω, F) and two measures µ, ν on (Ω, F), the total variation distance TV (µ, ν) between µ and ν is defined as TV (µ, ν) = sup |µ(A) − ν(A)| A⊆Ω

If Ω is a finite set, then TV (µ, ν) =

1X |µ({x}) − ν({x})| 2 x∈Ω

In particular, for two probability mass functions P and Q on a finite set then TV(P, Q) =

1X P (x) − Q(x) . 2 x

Given two random variables X and Y over a finite set Ω with probability mass functions PX and QY , respectively, we abuse notation and denote as TV (X, Y ) the total variation distance between PX and QY , i.e., TV (PX , QY ). Now we define statistical indistinguishability. Definition 2. Two random variables X and Y defined over the same set A with size |A| = q are said to be statistically indistinguishable iff for every polynomial p X TV (X, Y ) = |P [X = z] − P [Y = z] | ≤ 1/p(n) z∈A

where n is a given parameter5 . The following are known and standard properties of the total variation distance. Property 1 ([CT06]). For three random variables X, Y, Z on Fq , where Z is independent from X and Y, TV (X · Z, Y · Z) ≤ TV (X, Y) i.i.d.

Property 2 ([TV06]). Let X1 , . . . , Xh ∼ Unif(Fq ). Then, ! Y h TV Xi , Unif(Fq ) = O . q i

Property 3 ([Dur19]). Let X, Y be two random variables on Fq and {Ei }i∈[k] a partition of events. Then TV (X, Y) =

k X

P [Ei ] · TV (X|Ei , Y|Ei )

i=1

2.1

Distributed interactive proofs and distributed zero-knowledge proofs

A distributed language L is a set of pairs (G, I) where • G = (V, E) is a connected communication graph, • I : V → {0, 1}∗ is a function such that I(v) represents the input to v (e.g., the weights of edges incident to v, or the identifier of v). In this paper, the input label I(v) always contains the unique identifier of v ID(v) ∈ {0, 1, . . . , n − 1}, and the ID of its parent in an arbitrary spanning tree rooted a the node with ID 0. For integer k ∈ {0, . . . , n − 1} the node k means the node v with ID(v) = k. Our verification model for a distributed language follows the distributed interactive proof (dIP) framework introduced by Kol, Oshman, and Saxena [KOS18]. Informally, the n nodes of a connected communication network G = (V, E) act as a (distributed) verifier who may interact with a single powerful but untrusted prover. A distributed interactive proof is parametrized by 5

In this work, n is always a number of nodes in a distributed network.

• the number of rounds r of interactions between nodes and the prover. • the number of bits ℓ in the messages exchanged between each node and the prover. • the class AV of distributed verification algorithms. Therefore we refer to it as a (r, ℓ, AV )-distributed interactive proof, or simply (r, ℓ, AV )-dIP. An (r, ℓ, AV )-dIP proceeds as follows. First, the network and the prover interact in r rounds, such that the final round is the prover’s round. In each round, the prover sends each node a message of ℓ-bit (if it is the prover’s round) or each node sends the prover a message of ℓ-bit (if it is the verifier’s round). After these interaction rounds, the network, without further communication with the prover, runs a verification algorithm A ∈ AV which decides the output of each node. Definition 3. The class dIP[r, ℓ, AV ] is defined as all the distributed languages L such that there exists an (r, ℓ, AV )-distributed interactive proof for L satisfying the following conditions: Completeness: If (G, I) ∈ L, there exists a prover that makes all nodes output “accept” with probability at least 2/3. Soundness: If (G, I) ∈ / L, for any prover, all nodes output “accept” with probability at most 1/3. Throughout this work, the class AV of verification algorithms will always be a class of distributed algorithms C[O(1), rℓ] that run in O(1) synchronous rounds, and in each round the neighbors exchange messages of size at most O(rℓ) bits. Note that in the original definition [KOS18] the class was further limited to one-round algorithms. 2.1.1

Zero-knowledge property

In this work, we study distributed zero-knowledge interactive proofs against an honest but curious node. This means that each node will not deviate from the prescribed protocol, but cannot learn anything from the information provided by the prover and the rest of the nodes. Motivated by the definition of perfect zero-knowledge in the centralized setting, [BKO22] introduced the notion of distributed zero-knowledge proofs. Following [BKO22, GPP25], the view of a node v in a distributed interactive proof is defined as follows. Definition 4 (View of a node v, [BKO22]). Given a graph (G, I) and a dIP Π, the view of a node v ∈ V is defined by a random variable VIEW(Π, G, I)v that contains all the values given to the node v, either by the prover or by its neighbors during the protocol Π. VIEW v denotes the distribution of VIEWv . In order to formally define the notion of distributed zero-knowledge, it is necessary to consider an additional class of distributed algorithms AS , that is, a class of simulators. (However, throughout this work, the class is always identical to AV .) As in the original definition of dZK given in [BKO22], the notion of zero-knowledge can be extended for a coalition of nodes, but we focus on the most fundamental case: zero-knowledge against coalitions of size one. Therefore the definition of zero-knowledge to be used in this work is the following. Definition 5 (dZK for coalitions of size one, [BKO22] and [GPP25]). Let r, ℓ ∈ N and let AV , AS be non-empty sets of distributed algorithms. The class dZK[r, ℓ, AV , AS ] is the set of all distributed languages L, for which there exist an (r, ℓ, AV )-distributed interactive proof system such that there exists a simulator S ∈ As such that for every node v ∈ V , it holds that (OUTS (G, I))v ≡ (VIEW(Π, G, I))v 16

where the equality holds in distribution, (OUTS (G, I))v corresponds to the distribution of the view of node v in the simulator. This definition of zero-knowledge given in [BKO22] is a distributed adaptation of the notion of perfect zero-knowledge in the centralized interactive proofs, in which we ask for the existence of a simulator such that the view of each node after the execution of the simulator has the same distribution as the view obtained during a real execution of the interactive proof. Following the definition of statistical zero-knowledge proofs in the centralized setting [GMR89], in which we now ask for the existence of a simulator such that the view of each node after the execution of the simulator is statistically close to the distribution of its view in the interactive proof real distribution. The notion of distance between different distributions is the total variation distance (see Definition 1). , we define the class of statistical zero-knowledge distributed proofs, which we call dStatZK, defined as follows Definition 6 (dStatZK). Let r, ℓ ∈ N and let AV , AS be non-empty sets of distributed algorithms. The class of distributed statistical zero-knowledge proofs dStatZK[r, ℓ, AV , AS ] is defined as the set of all distributed languages L, for which there exist an (r, ℓ, AV )-distributed interactive proof system and a simulator S ∈ AS that satisfy the following statistical zero-knowledge property: The two distributions (OUTS (G, I))v and (VIEW(Π, G, I))v are statistically indistinguishable (Definition 2). In the special case of AV = AS , we refer to the class dStatZK[r, ℓ, AV , AS ] simply as dStatZK[r, ℓ, AV ].

Sumcheck Protocol: General Framework.

Assume that we are given oracle access to a polynomial F : FN → F of total degree d and individual degree O(n) and N variables. The Sumcheck protocol, originally due to Lund, Fortnow, Karloff, and Nisan [LFKN92], verifies the value of a large summation of F over the Boolean hypercube {0, 1}N , converting a claim about the sum of 2N polynomial evaluations to a single evaluation at a randomly chosen point. Below we briefly describe the protocol, which is the same as the one presented in Section 1.3. Protocol 3.1: Sumcheck-Protocol N Input: A polynomial P F : Fq → Fq of total degree d, and a field element a ∈ Fq . Goal: Check that x∈{0,1}N F (x) = a.

Theorem 6 (Completeness and Soundness, [LFKN92]). The Sumcheck protocol satisfies: P • Completeness: If x∈{0,1}N F (x) P = a, the honest prover can convince the verifier with probability 1 by sending gi (xi ) = xi+1 ,...,xn ∈{0,1} F (r1 , . . . , ri−1 , xi , . . . , xn ). P • Soundness: If x∈{0,1}N F (x) ̸= a, for any (cheating) prover the verifier rejects with probability at least 1 − Nq·d . The proof follows from the standard polynomial identity test: at the first round in which gi is not the correct partial sum, the polynomial sent differs from the honest one by a non-zero degree-d polynomial, which vanishes at most d points due to Schwartz-Zippel Lemma. The random check catches this with probability 1 − d/q. An union bound over the N rounds yields the claimed error bound. See [LFKN92] for more detail.

3.1

The Distributed Implementation

We address how to solve a general instance of the distributed Sumcheck protocol. Formally, the problem that we address is the following. Sumcheck-problem Input. A Sumcheck-instance (G, F, q, a), where G is an n-node communication graph of the distributed verifier, F : FN q → Fq is a polynomial of individual degree at most O(n), q is a prime number representing the size of Fq and a value a ∈ Fq . Assumption. An Oracle access to F and an arbitrary spanning tree T of G. P P Decision problem: Decide if x∈{0,1}N F (x) = a or not: If x∈{0,1}N F (x) = a, all nodes accept; otherwise, at least one node rejects. In this problem, we just assume oracle access to F and ignore how to realize it. Later, when the applications of this framework are explained, we will address how to evaluate F for each concrete problem. As a warm-up, let us first discuss how to simulate each round of Protocol 3.1 using a distributed interactive proof without zero-knowledge guarantees. Here, the prover is required to send an univariate polynomial gi , which is allegedly equal to X F (r1 , . . . , ri−1 , x, xi+1 , . . . , xN ). xi+1 ∈{0,1},...,xN ∈{0,1}

Since the individual degree of F is O(n), this polynomial has degree at most O(n) (for simplicity, we assume that the degree is less than n). Therefore alleged gi must be specified by n field P (i) j elements that represent coefficients: gi (x) = n−1 j=0 αj x . In the protocol, the prover distributes (i)

these coefficients to the nodes, so that each node k receives a single field element αk . In case of O(n)-degree, each node receives O(1) coefficients. For the initially given spanning tree T , let child(k) be the set of children of k in T and Tk be the subtree of T with the root k. We now explain the verification phase of the protocol. Simulating Step 1. Step 1 of Sumcheck protocol checks that g1 (0) + g1 (1) = a. Since g1 (x) = P (1) k Pn−1 (1) (1) k αk x , it is equivalent to checking 2α0 + k=0 αk = a. To this end, we introduce a P (1) (1) value βk provided by the prover to node k, which is allegedly equal to j∈Tk αj . The correctness of this value is checked as follows, by 1-round communication. 18

• If child(k) = ∅ (k is a leaf in T ), k checks that (1)

(1)

αk = βk

(3)

• If k is not a leaf, checks that (1)

βk = αk +

(1)

βj

(4)

j∈child(k) (1)

where βj

is sent from j.

• If k is the root of the tree, i.e., k = 0, it also checks that (1)

(1)

α0 + β0 = a.

(5)

If all these tests passed, then g1 (0) + g1 (1) = a. Simulating Step 2. Fix arbitrary i. Step 2 of Sumcheck protocol checks that gi (0) + gi (1) = gi−1 (ri−1 ). This is equivalent to checking (i)

α0 +

n−1 X

(i)

αk =

k=0

n−1 X

(i−1) k ri−1 .

αk

k=0

g (i) (i) To this end, we introduce βk and βk provided by the prover to node k, allegedly satisfying: X (i) (i) βk = αk′ k′ ∈Tk

X (i−1) ′ g (i) k . βk = αk′ ri−1 k′ ∈Tk

Similarly to the simulation of Step 1, the correctness of these values can be checked using g (i) (i) (i) (i) k . If k is not a leaf, the tree T : If k is a leaf, checks that αk = βk and βk = αk · ri−1 checks that X (i) (i) (i) βk = αk + βj j∈child(k)

and g (i) (i−1) k βk = αk · ri−1 +

g (i) βj

j∈child(k)

g (i) (i) (i) (i) where βj and βj are sent from j. Then node k = 0 additionally checks that α0 + β0 = g (i) β0 . Simulating Final Check. Final Check of Sumcheck protocol verifies that indeed the equality gN (rN ) = F (r1 , . . . , rN ) holds. As in the simulation of Step 1 and Step 2, gN (rN ) can be computed using the tree T , and oracle access to F (from our assumption) gives the value of F (r1 , . . . , rN ).

The distributed implementation of the Sumcheck protocol described above follows the same sequence of steps as the centralized algorithm in Protocol 3.1, but propagates intermediate data along a rooted spanning tree of the communication graph. Therefore, it is not zeroknowledge because, through intermediate computations, the verifier learns the coefficients of internal polynomials and the evaluations of each internal polynomial gi for random values chosen by the verifier. Specifically, the root node receives the evaluation of gi . Since the original polynomial encodes global information, learning these values leaks information of the graph, which is impossible to learn for the class of simulators C[O(1) , O(N log q)], which we regard as efficient. To resolve this issue, we show how to simulate each step of the distributed implementation described above, keeping these values secret from the nodes.

3.2

General Toolbox for the zero-knowledge simulation.

Before describing the formal modification of Sumcheck, we describe the main technical modifications that will be done to the original algorithm in order to hide the coefficients and partial sums. Regarding the implementation of Steps 1 and 2 in Sumcheck Protocol, in both cases the original implementation must ensure that each node receives the appropriate coefficients of the univariate polynomials defined by: X

f (r1 , . . . , ri−1 , x, xi+1 , . . . , xN ).

xi+1 ∈{0,1},...,xN ∈{0,1}

As previously discussed, revealing the coefficients of these polynomials may inadvertently leak information that cannot be simulated by any algorithm in the class C[O(1) , O(log n)]. Nonetheless, it is still necessary to verify that certain conditions hold for these polynomials such as Equations 3, 4, and 5. The technique used to encrypt the sum of coefficients is fairly standard in the context of secure multiparty computation (MPC) [Sha79, RBO89], and has been employed in previous distributed zero-knowledge implementations as well (e.g., for 3-coloring in [BKO22]). However, in our setting, a key difference that must be addressed is that each value sent to a node may participate in more than one equation. This leads to a more intricate construction, which we develop incrementally, culminating in the complete protocol described in Section 3.5. A central tool is the use of a polynomial encryption of a value α ∈ Fq . Definition 7. Given a field Fq with q prime and a value α ∈ Fq , a polynomial encryption of α is a degree-one polynomial, denoted as P [α] ∈ Fq [x], such that P [α] is built by sampling an uniform value r ∼ Unif(Fq ) and P [α](x) = r · x + α The following standard fact about interpolation of a degree-one polynomial holds. Fact 7. Given a field Fq and two different points y1 , y2 ∈ Fq , there exists a unique polynomial P (x) ∈ F1q [x], where F1q [x] is the set of all degree-one polynomials over Fq , such that both y1 and y2 are in the image of P (x) in Fq . Fact 7 states that knowing two evaluations of the polynomial enables us to reconstruct such a polynomial due to its uniqueness (for example, through interpolation). In fact, the following property is crucial to obtain a constant round simulator for both Steps.

Proposition 1. Given α ∈ Fq , P [α] its polynomial encryption and an polynomial N ∈R F1q [x] chosen uniform at random, then for any β ∈ Fq , the distribution of the random variable δ : = P [α](β) + N (β) is uniform in Fq . Proof. Fix β ∈ Fq . Since P [α] is fixed once α is fixed, the value P [α](β) is a fixed element of Fq . Hence it is enough to prove that N (β) is uniformly distributed over Fq . Write N (x) = ax + b, where a, b ∈ Fq are chosen uniformly at random subject to N ∈R F1q [x]. For any fixed value z ∈ Fq , the condition N (β) = z is equivalent to aβ + b = z. For every admissible choice of a, there is a unique value of b, namely b = z − aβ, satisfying this equation. Therefore, the number of polynomials N ∈ F1q [x] such that N (β) = z is the same for every z ∈ Fq . Consequently, N (β) is uniformly distributed over Fq . Finally, δ = P [α](β) + N (β) is obtained by adding the fixed field element P [α](β) to a uniformly distributed random variable. Since translation by a fixed element is a bijection of Fq , δ is also uniformly distributed over Fq . 3.2.1

Zero-knowledge implementation of Step 1.

Without loss of generality, we assume that the sum to be verified is 0. Recall in Step 1 each node P P (1) (1) k (1) (1) (1) k ∈ V receives two values αk , βk ∈ Fq where g1 (x) = n−1 j∈Tk αj for k=0 αk x and βk = the subtree Tk with root k, and in the verification phase each node k needs to verify (1)

(1)

βk = αk +

(1)

βj

(6)

j∈child(k)

and node k = 0 also needs to verify that (1)

(1)

α0 + β0 = 0.

(7)

Given the complexity of these technical aspects, we first detail how Step 1 can be implemented using a protocol satisfying the perfect zero-knowledge property, and subsequently describe how to extend this approach to handle Step 2 while preserving the same guarantees. 3.2.1.1

(1)

Random Additions.

(1)

In order to conceal the values αk and βk from the nodes, h i h i (1) (1) the prover computes a random polynomial encryption, denoted by P αk and P βk . Additionally, for each h iof thesehvalues, i the prover independently samples random polynomials of (1) (1) degree one, N αk (x), N βk (x) ∈R F1q [x] for node k. The coefficients of these random (1)

(1)

polynomials do not depend on αk or βk . The only constraint imposed on the resulting family of polynomials is the following condition:

(RC)1

h i (1) N αk (0) +

h i h i (1) (1) N βj (0) = N βk (0)

∀k ∈ V

(8)

j∈child(k)

After the prover computes these polynomials, the simulation of Step 1 is done by checking Wk (0) = 0 where h i h i h i h i h i X h (1) i (1) (1) (1) (1) (1) Wk (x) = P αk + N αk (x)− P βk + N βk (x) (x)+ P βj + N βj j∈child(k)

(9)

since the condition (RC)1 gives (1)

Wk (0) = 0 ⇐⇒ αk +

(1)

βj

(1)

= βk .

(10)

j∈child(k)

Each node k needs to reconstruct Wk (x) without knowing polynomial encryptions. This is achieved as follows. The prover sends to each node k the following values, where ck ∈ {1, 2} is the color of k in a random 2-coloring of T : h i h i h i h i (1) (1) (1) (1) • P αk (ck ), N αk (ck ), P βk (ck ), N βk (ck ) h i h i h i h i (1) (1) (1) (1) • P αp (ck ), N αp (ck ), P βp (ck ), N βp (ck ) of its parent p in the spanning tree T h i h i (1) (1) • P βj (ck ), N βj (ck ) of each child j in the spanning tree T . Once the prover sends them, the node k sends its parent p h i h i h i h i (1) (1) (1) (1) • P αk (ck ) + N αk (ck ), P βk (ck ) + N βk (ck ) h i h i h i h i (1) (1) (1) (1) • P αp (ck ) + N αp (ck ), P βp (ck ) + N βp (ck ) h i h i h i h i h i (1) (1) (1) (1) (1) (1) to reconstruct the polynomials P αk + N αk , P βk + N βk , P [αj ] + N αj for each children j. Now, the node k can locally compute Wk (x). This strategy allows nodes to (1) (1) verify whether Equation (6) holds without revealing the labels αk and βk . Nevertheless, this approach introduces three immediate drawbacks that must be addressed. Problem 1. The nodes cannot reconstruct the random polynomials sent by the prover, and therefore cannot trust that the prover in fact sent them random polynomials satisfying condition (RC)1 . Problem 2. As each node can have up to Ω(n) children, the message size is O(n log q) bits. Problem 3. The nodes were able to verify that Equation 6 is satisfied without revealing any of the coefficients, but we still need to verify that Equation 7 is satisfied, without having (1) (1) access to the values α0 and β0 . Problems 1 and 2 are standard and their solutions are included for the sake of completeness. We specifically address Problem 3. These techniques will appear again in the analysis of Step 2. 3.2.1.2 Cut and Choose Technique. To resolve Problem 1., we use the cut-and-choose technique, a classical tool used in zero-knowledge algorithms, which is also used in [BKO22]. This technique works as follows: Given a constant parameter t ∈ for h N, ithe prover h computes, i (1) (1) each node k ∈ V , t independent random copies of polynomials Nh αk and Nh βk satisfying condition (RC)1 for each hh∈ [t].i Then the prover h isends, in the first round of communication, (1) (1) to each node k a share Nh αk (ck ) and Nh βk (ck ) for each h ∈ [t] and sends the shares h i h i (1) (1) Nh αk (3 − ck ) and Nh βk (3 − ck ) to each children j of k. After the prover has committed the shares of these t copies, in round two the nodes select randomly one of these copies h(1) ∈ [t] 22

and send this value to the prover. Finally, in round three h thei prover sends h thei original messages (1) (1) described before, using the random polynomials Nh(1) αk and Nh(1) βk for each node k. For all the copies not selected, the nodes reconstruct the random polynomials by exchanging the shares with neighbors and verify that condition (RC)1 holds for each of these copies. The nodes rejects if some of them breaks condition (RC)1 . The copy h(1) selected is not revealed, and the nodes proceed with this copy to verify the respective equalities. As the prover didn’t know which of the t copies were to be used, the probability that the prover sent random polynomials not satisfying Equation (8) for the selected copy is at most 1/t. In the zero-knowledge protocol for Step 2, we also use extra random polynomials that must satisfy certain equations such as condition (RC)1 . Every time we send these polynomials, the protocol takes O(1) rounds and the message grows by a factor of t. Since t is a fixed constant, it does not affect the message size O(log n). 3.2.1.3

Messages of size O(log n)

To resolve Problem 2., we proceed analogously to nh h i h ii o (1) (1) , [BKO22]. Instead of sending to node k all the shares P βj + N βj (ck ) j∈child(k)

these shares are distributed among the children of k, and later the children are going to inform node k of these shares as follows. Assume that the children of k are ordered from j0 , . . . , j|child(k)|−1 according to its id (for example ordering of the id’s). Each child ji will receive from the prover the share i ian increasing h h (1) (1) P βji+1 (ck ), N βji+1 (ck ) of the next child ji+1 . In the verification phase, the node ji informs ii i h h h (1) (1) to node k the share P βji+1 + N βji+1 (ck ) of its consecutive child. 3.2.1.4 Same coefficient in different equalities. Finally, we deal with Problem 3. Using the above techniques the node 0 can verify W0 (0) = 0, which means X (1) (1) (1) α0 + βj = β0 j∈child(k)

h i (1) by Equation 10. Notice that at this point, the node 0 knows the polynomials P α0 + h i h i h i (1) (1) (1) (1) Nh(1) α0 and P β0 + Nh(1) β0 and does not know the coefficient α0 nor the value (1)

β0 , but still needs to verify Equation (5) which is equivalent to g1 (0) + g1 (1) = 0. The idea is to use extra random polynomials. The algorithm proceeds as follows. In the same round that the prover sent the shares of the t random polynomials, the prover also sends the shares of t extra random polynomials M1 , . . . , Mt to the node 0 and its children, such that the following condition holds. h i h i (1) (1) (0C)1 Mh (0) = Nh α0 (0) + Nh β0 (0), ∀h ∈ [t] Consider that the node 0 reveals Mh (x) for if h allih and checks h i the condition h i (0C)1 hholdsi for all (1) (1) (1) (1) (1) h ̸= h . Since the node 0 can recover P α0 + Nh(1) α0 and P β0 + Nh(1) β0 , h h i h i h i h i i (1) (1) (1) (1) P α0 + Nh(1) α0 + P β0 + Nh(1) β0 − Mh(1) (0) = 0 h i h i (1) (1) can be checked locally. This is identical to P α0 (0)+P β0 (0) = 0 under the condition that h h i h ii (1) (1) (0C)1 holds for h = h(1) . Note that this modification additionally reveals Nh(1) α0 + Nh(1) β0 (0), 23

(1)

resulting that the node 0 learns the value of α0 + β0 (but does not learn α0 and β0 ). Nevertheless, for any yes-instance this value is always equal to 0 (more precisely, a), and the zero-knowledge property survives.

3.3

Zero-knowledge implementation of Step 2.

We follow the similar approach for Step 1. Remember that each node k ∈ V needs to verify the following equalities X (i) (i) (i) βj (11) βk = αk + j∈ch(k)

X ^ g (i) (i−1) k (i−1) βk = αk ri−1 + βj ,

(12)

j∈ch(k)

and node k = 0 also needs to verify that g (i) (i) (i) α0 + β0 = β0 .

(13)

The main difference is that we have to use the coefficients from the previous round to check Equation (12). To this end, we further modify the cut-and-choose technique. We assume h that i (i−1) 2 , in the phase i − 1 the prover actually sent t copies of each random polynomial Nh αk h i (i−1) , instead of t copies. The verifier then selected t2 − t − 1 indices to be opened to check Nh β k the consistency condition. Among the remaining t + 1 copies, the verifier selects one index h(i−1) (i−1) to check the condition ii Equation (11). Consequently, we have t possible h involving h i αk h, namely, (i−1)

(i−1)

(x) for t different indices from [t2 ], relabel them g (i) by [t]. Now in the phase i, given the random value ri−1 ∈ Fq , random polynomials Nh βk for

options of the form P αk

+ N h αk

g (i) hiding βk satisfy h i (i−1) k Nh αk (0) · ri−1 +

g g (i) (i) βj (0) − Nh βk (0) = 0.

(14)

j∈child(k)

Once the above condition is ensured, checking Equation (12) is done by checking h i X g g g g (i) (i) (i−1) (i−1) (i) (i) k P [βk ] + Nh [βk ] (0) = P [αk ] + Nh [αk ] (0) · ri−1 + P [βj ] + Nh [βj ] (0) j∈child(k)

(15) where each polynomial in Equation (15) is reconstructed by the node k. Finally, to check Equation (13), we introduce random polynomials Mx,y for x ∈ [t2 ], y ∈ [t] such that h i h i g (i) (i) (i) Mx,y (0) = Nx α0 (0) + Nx β0 (0) − Ny β0 (0). Once we have this relation Equation (13) is checked by h h i h ii h h i h ii g g (i) (i) (i) (i) (i) (i) P α0 + Nx α0 (0) + P β0 + Nx β0 (0) − P β0 + Ny β0 (0) = Mx,y (0).

3.4

Zero-knowledge implementation of Step 3 and final application.

Assuming that the nodes to query the value f (r1 , . . . , rN ), the node k = 0 h have i oracle access h i (N ) (N ) has the polynomial P αk + Nh(N ) αk (ck ) selected in the final phase of Step 2.

3.5

Final protocol

Now we describe the interaction between the prover and the nodes for each step of our zeroknowledge implementation of Sumcheck and the corresponding verification procedures. Prover-Verifier Interaction Π1 for Step 1 1. Precomputation of the honest prover for each node k: P1. A random 2-coloring {ck }k∈V of the spanning tree. Then ck is an uniform random variable in {1, 2} for all k ∈ V . h i h i n h i h io (1) (1) (1) (1) P2. Polynomial encryption P αk , P βk and Nh αk , Nh βk ⊆R F1 [x] h∈[t2 ] h i h i P (1) (1) such that Nh αk (0) = − j∈child(k) Nh βj (0) for all h ∈ [t2 ]. The prover also h i h i (1) (1) computes {Mh }h∈[t2 ] ∈R F1 [x] such that Mh (0) = Nh β0 (0) + Nh α0 (0) for all h ∈ [t2 ]. 2. Message from the honest prover to each node k: h i h i h i h i (1) (1) (1) (1) M1. Sends the shares P αk (ck ), Nh αk (ck ), P βk (ck ), Nh βk (ck ) for each h ∈ [t2 ]. h i h i (1) (1) M2. If p is its parent in the ST, the prover also sends the shares P αp (ck ), Nh αp (ck ) i i h h (1) (1) and P βp (ck ), Nh βp (ck ) for each h ∈ [t2 ]. h i h i (1) (1) M3. If k has a unique child j, the prover also sends the shares P αj (ck ), Nh αj (ck ) h i h i (1) (1) and P βj (ck ), Nh βj (ck ) for each h ∈ [t2 ]. h i (1) M4. If k has a next sibling k ′ in the ST, the prover also sends the shares P αk′ (3 − ck ), h i h i h i (1) (1) (1) Ph αk′ (3 − ck ) and P βk′ (3 − ck ), Nh βk′ (3 − ck ) for each h ∈ [t2 ]. M5. If k = 0, for all h ∈ [t2 ], the prover sends the description of Mh to the node 0. (1)

(1)

3. Message from the root of ST to the prover: Selects t + 1 indices h0 , . . . , ht uniform at random and sends to the prover. (1)

(1)

4. Message from the honest prover to each node k: The prover tells h0 , . . . , ht

∈ [t2 ]

to each node.

Verification Protocol of Π1 (Communication) Each node k in one round: h h i h ii h h i h ii (1) (1) (1) (1) C1. Sends to its parent p the shares P βk + Nh(1) βk (ck ), P αp + Nh(1) αp (ck ), 0 0 h h i h ii (1) (1) (1) (1) 2 P βp + Nh(1) βp (ck ). For each index h ∈ [t ]\{h0 , . . . , ht }, sends to p the shares 0

h i h i h i h i (1) (1) (1) (1) Nh αk (ck ), Nh βk (ck ), Nh αp (ck ), and Nh βp (ck ) . If k has the next sibling k ′ , h ii h i h h i (1) (1) (1) (3−ck ), and Nh αk′ (3−ck ), then sends to its parent p the share P βk′ + Nh(1) βk′ 0 i h (1) (1) (1) 2 Nh βk′ (3 − ck ) for h ∈ [t ]\{h0 , . . . , ht }. (Verification) Each node k ∈ V verifies the following. h i h i h i (1) (1) (1) (1) (1) V1. For all h ∈ [t2 ]\{h0 , . . . , ht }, interpolates Nh αk , Nh βk , and Nh βj for j ∈ child(k) to check h i (1) Nh αk (0) +

h i h i (1) (1) Nh βj (0) = Nh βk (0).

X j∈child(k)

(1)

If k = 0 it also checks for each h ∈ [t2 ]\{h0 , . . . , ht } h i h i (1) (1) Mh (0) = Nh α0 (0) + Nh β0 (0). h h i h ii h h i h ii (1) (1) (1) (1) V2. Interpolates the polynomials P βk + Nh(1) βk (x), P αj + Nh(1) αj (x) and 0 0 h h i h ii (1) (1) P βj + Nh(1) βj (x) for each j ∈ child(k) and checks that 0

ii i h h h (1) (1) (0) + P αk + Nh(1) αk

h h i h ii (1) (1) P βj + Nh(1) βj (0)

j∈child(k)

ii i h h h (1) (1) (0) = P βk + Nh(1) βk 0

V3. If k = 0, also verifies the following equality: h h i h ii h h i h ii (1) (1) (1) (1) P α0 + Nh(1) α0 (0) + P β0 + Nh(1) β0 (0) = Mh(1) (0) 0

Prover-Verifier Interaction Π2 for Step 2 For each i ∈ {2, . . . , N }, the prover and the verifier act as follows. (i−1) (i−1) h1 , . . . , ht ∈ [t2 ] from the previous round by {1, . . . , t}.

Rewrite the indices

1. Message from the root of ST to the prover: Selects ri−1 ∈ Fq uniform at random and sends to the prover. 2. Local computation of the honest prover for each node k: h i h i g (i) (i) (i) P1. Polynomial encryption P αk , P βk , P βk . n h i h io (i) (i) P2. Random polynomials Nh αk , Nh βk ⊆R F1 [x] such that h∈[t2 ]

(i)

Nh αk P3. Random polynomials

h i (i) (0) = −Σj∈child(k) Nh βj (0).

g (i) Nh β k

⊆R F1 [x] such that

h∈[t]

h i (i−1) k Nh αk (0) · ri−1 +

X j∈child(k)

g g (i) (i) Nh βj (0) − Nh βk (0) = 0

h i (i−1) } by [t] for Nh αk (0). h i (i) P4. Random polynomials {Mx,y }x∈[t2 ],y∈[t] ⊆R F1 [x] such that Mx,y (0) = Nx α0 (0) + h i g (i) (i) Nx β0 (0) − Ny β0 (0). (i−1)

where we relabeled the indices {h1

(i−1)

, . . . , ht

3. Message from the honest prover to each node k: h i g (i) (i) M1. Sends the value ri−1 and the shares P (ck ), P βk (ck ), P βk (ck ), h i h i g (i) (i) (i) 2 Nh αk (ck ), Nh βk (ck ) for each h ∈ [t ] and Nh βk (ck ) for each h ∈ [t]. h i h i (i) (i) M2. If p is its parent in the ST, the prover also sends the shares P αp (ck ), P βp (ck ), h i h i g g (i) (i) (i) (i) 2 P βp (ck ), Nh αp (ck ), Nh βp (ck ) for each h ∈ [t ] and Nh βp (ck ) for each h

(i) αk

h ∈ [t]. h i h i (i) (i) M3. If k has a unique child j, the prover also sends the shares P αj (ck ), P βj (ck ), h i h i g g (i) (i) (i) (i) P βj (ck ), Nh αj (ck ), Nh βj (ck ) for each h ∈ [t2 ] and Nh βj (ck ) for each h ∈ [t]. h i (i) M4. If k has a next sibling k ′ in the ST, the prover also sends the shares P αk′ (ck ), h i h i h i g (i) (i) (i) (i) P βk′ (ck ), P βk′ (ck ), Nh αk′ (ck ), Nh βk′ (ck ) for each h ∈ [t2 ] and g (i) Nh βk′ (ck ) for each h ∈ [t]. M5. If k = 0, for all h ∈ [t], the prover sends the description of Mx,y for x ∈ [t2 ] and y ∈ [t]. (i)

(i)

4. Message from the root of ST to the prover: Selects t + 1 indices h0 , . . . , ht ∈ [t2 ], and an index h(i) ∈ [t] uniform at random and sends to the prover. 5. Message from the honest prover to each node k: The prover tells h0 , . . . , ht ∈ [t2 ] and h(i) to each node.

Verification Protocol of Π2 For each i ∈ {2, . . . , N }, the verification protocol is as follows. (Communication) Each node k in one round: h h i h ii (i) (i) (i) (ck ), C1. For h = h0 , sends to its parent p the shares P αk + Nh αk h h i h ii h h i h ii h h i h ii (i) (i) (i) (i) (i) (i) P β + N h βk (ck ), P αp + Nh αp (ck ), P βp + Nh βp (ck ) and h h k i h ii (i) (i) P βk′ + Nh βk′ (3 − ck ) if k has a next sibling k ′ . For each index h ∈ h i h i (i) (i) (i) (i) [t2 ]\{h0 , . . . , ht }, sends to p the shares Nh αk (ck ), Nh βk (ck ). (Verification) Each node k ∈ V verifies the following.

(i)

V1. Checks that for all h ∈ [t2 ]\{h0 , . . . , ht }, h i h i i h X (i) (i) (i) Nh βj (0) = Nh βk (0). Nh αk (0) + j∈child(k)

V2. Checks that for all h ∈ [t]\{h(i) }, h i g (i) (i−1) k Nh βk (0) = Nh αk (0) · ri−1 +

g (i) Nh βj (0).

j∈child(k) (i)

(i)

V3. If k = 0, checks that for all x ∈ [t2 ]\{h0 , . . . , ht } and y ∈ [t]\{h(i) }, h i h i g (i) (i) (i) Mx,y (0) = Nx α0 (0) + Nx β0 (0) − Ny β0 (0). h h i h ii h h i h ii (i) (i) (i) (i) V4. Interpolates the polynomials P βk + Nh(i) βk (x), P αk + Nh(i) αk (x) and 0 0 h ii h h i (i) (i) (x) for each j ∈ child(k) and checks that P βk + Nh(i) βk 0

h h i h ii (i) (i) P αk + Nh(i) αk (0) +

h h i h ii (i) (i) P βj + Nh(i) βj (0)

j∈child(k)

ii i h h h (i) (i) (0) = P βk + Nh(i) βk 0

h h i h ii g g (i−1) (i−1) (i) (i) V5. Interpolates the polynomials P αk + Nh(i) αk (x), P βk + Nh(i) βk (x) g g (i) (i) and P βj + Nh(i) βj (x) for each j ∈ child(k) and checks that h h i h ii (i−1) (i−1) k P αk + Nh(i) αk (0) · ri−1 +

g g (i) (i) (0) P βj + Nh(i) βj

X j∈child(k)

g g (i) (i) (0) = P βk + Nh(i) βk V6. If k = 0, also verifies the following equality: h h i h ii h h i h ii g g (i) (i) (i) (i) (i) (i) P α0 + Nh(i) α0 (0) + P β0 + Nh(i) β0 (0) − P β0 + Nh(i) β0 (0) 0

= Mh(i) ,h(i) (0) 0

Prover-Verifier Interaction Π3 for Final Check (N )

(N )

Rewrite the indices h1 , . . . , ht

∈ [t2 ] from the previous round by {1, . . . , t}.

1. Message from the root of ST to the prover: Selects rN ∈ Fq uniformly at random, and sends to the prover. 2. Local computation of the honest prover for each node k:

^ (N +1) P1. Polynomial encryption P βk . P2. random polynomials

^ (N +1) Nh βk

⊆R F1 [x] such that

h∈[t]

(N ) Nh αk

k (0) · rN +

^ ^ (N +1) (N +1) Nh β j (0) − Nh βk (0) = 0

X j∈child(k)

n h i o (N ) where Nh αk (0) were determined in the previous round. Especially for h∈[t] ] (N ) k = 0, set Nh β0 (0) = 0. 3. Message from the honest prover to each node k: ^ ^ (N +1) (N +1) M1. Sends the shares P βk (ck ), Nh βk (ck ) for each h ∈ [t]. ^ (N +1) M2. If p is its parent in the ST, the prover also sends the shares P βp (ck ), ^ (N +1) Nh βp (ck ) for each h ∈ [t]. ^ (N +1) M3. If k has a unique child j, the prover also sends the shares P βj (ck ), ^ (N +1) Nh βj (ck ) for each h ∈ [t]. ^ (N +1) M4. If k has a next sibling k in the ST, the prover also sends the shares P βk′ (3−ck ), ^ (N +1) Nh βk′ (3 − ck ) for each h ∈ [t]. ′

4. Message from the root of ST to the prover: Selects an index h(N +1) ∈ [t] uniform at random and sends to the prover. 5. Message from the honest prover to each node k: The prover tells h(N +1) to each node.

Verification Protocol of Π3 For each i ∈ {2, . . . , N }, the verification protocol is as follows. (Communication) Each node k in one round: h ii h h i (N ) (N ) (ck ), C1. Sends to its parent p the shares P αk + Nh(N +1) αk h h i h ii h h i h ii (N ) (N ) (N ) (N ) P αp + Nh αp (ck ) and P αk′ + Nh βk′ (3 − ck ) if k has a next h i (i) sibling k ′ . For each index h ∈ [t]\{h(N +1) }, sends to p the shares Nh αk (ck ), h i (i) Nh βk (ck ). (Verification) Each node k ∈ V verifies the following.

V1. Checks that for all h ∈ [t]\{h(N +1) }, h i ^ (N +1) (N ) k Nh β k (0) = Nh αk (0) · rN +

^ (N +1) Nh β j (0),

j∈child(k)

^ (N +1) and if k = 0, also checks that Nh βk (0) = 0. ^ ^ (N +1) (N +1) V2. Interpolates the polynomials P βk + Nh(N +1) βk (x), h ii h h i ^ ^ (N ) (N +1) (N +1) (N ) (x), P βj + Nh(N +1) βj (x) for each P αk + Nh(N +1) αk j ∈ child(k) and checks that h ii h h i (N ) (N ) k (0) · rN + P αk + Nh(N +1) αk

^ ^ (N +1) (N +1) P βj + Nh(N +1) βj (0)

X j∈child(k)

^ ^ (N +1) (N +1) = P βk + Nh(N +1) βk (0) V3. If k = 0, checks the following equality: ^ ^ (N +1) (N +1) P β0 + Nh(N +1) βk (0) = f (r1 , . . . , rN ) by using oracle access to f .

3.6

Completeness and Soundness

Let us now analyze the protocol presented in Section 3.5. Assume that the prover follows the honest strategy. P (1) (1) (1) Protocol Π1 : In V2. of Π1 , each node k checks αk + j∈child(k) βj = βk , and in V3. of (1)

(1)

Π1 , the node k = 0 also checks α0 + β0 = 0. P (i) (i) (i) Protocol Π2 : In V4. and V5. of Π2 , each node k checks αk + j∈child(k) βj = βk and P g g (i−1) k (i) (i) αk · ri−1 + j∈child(k) βj = βk , respectively. In V6. of Π2 , the node k = 0 also checks g (i) (i) (i) α0 + β 0 = β 0 . P ^ ^ (N +1) (N ) (N +1) Protocol Π3 : In V2. of Π3 , each node k checks βk = αk · rnk + j∈child(k) βj , and in ^ (N +1) V3. of Π3 , the node k = 0 also checks β0 = f (r1 , . . . , rN ). To summarize, Π1 , Π2 , Π3 exactly simulate the distributed Sumcheck protocol. The completeness thus follows directly from the completeness of the Sumcheck protocol. For soundness, we first observe that if the malicious prover sends the random polynomials that do not satisfy the conditions checked in the verification protocol (more precisely, V1. in the verification protocol of Π1 , V1., V2., V3 in the verification protocol of Π2 , and V1. in the verification protocol of Π3 ), the acceptance probability is at most 1/t. We thus focus on the case that the prover sends the correct random polynomials. In this case, by construction of our 30

protocol the nodes check the same conditions checked in the distributed Sumcheck described in ) Section 3, and thus the acceptance probability is at most N ·deg(F where deg(F ) is individual q degree of F , by the soundness of Sumcheck (Theorem 6). The existence of the simulator. With these detailed analysis, it is straightforward to observe that all the messages received from the prover and the neighbors are masked by random polynomials, hence uniformly at random. Therefore, the simulator merely generates uniform random values for its output (and a single oracle query to F ), which exactly simulates the distribution of the real transcript. It is obvious that the verification algorithm is in the class C[O(1) , O(N log q)] since all the verification parts in the protocol Π1 , Π2 , and Π3 can be parallelized. Moreover, it is easy to see the simulator is also in the same class: it require only O(1) rounds of communication between neighboring nodes to allow each node to learn the IDs of its parent and children, as well as its next sibling (if any) in the spanning tree. The rest of the simulator simply samples uniformly at random values (satisfying required conditions), and a single oracle query to F used for Final Check. This completes the proof of Theorem 1.

Applications of Distributed Sumcheck

In this section, we prove Theorem 2 and Theorem 3, and provide formal statements of these results in terms of the statistical zero-knowledge dIP (dStatZK) class defined in Definition 6. To address these applications, we do not treat oracle access to the polynomials defined in Non-3-Colorability and subgraph-counting(H) as a black box; instead, we describe how these evaluations can be performed. Recall that we assume that each node knows the identifier of its parent in an arbitrary rooted spanning tree written in the input label, as mentioned in the definition of distributed languages in Section 2.1. Therefore, we can explicitly evaluate each polynomial by the nodes along the spanning tree with the assistance of the prover (see Section 4 for details). Consequently, to establish Theorem 2 and Theorem 3, it remains only to show how these evaluations can be simulated by the simulator. The key result of this section, and the reason why our protocol achieves statistical zero-knowledge rather than perfect zeroknowledge, is that we can guarantee only that each message used to compute one evaluation of the polynomials is statistically indistinguishable from the uniform distribution.

4.1

Non-k-Colorability

In this section, we study the problem Non-k-Colorability. The formal definition of the problem is below. Protocol 4.1: Non-k-Colorability Input. An n-node graph G = (V, E), with unique identifiers {0, . . . , n − 1}. Each node knows fixed integer k and the ID of its parent in an arbitrary spanning tree rooted at node with ID 0. Decision problem: Decide if the graph G does not admit a k-coloring. Here given a graph G = (V, E), a k-coloring of G is a function c : V → {1, . . . , k} such that for all {u, v} ∈ E, c(u) ̸= c(v). We prove the following theorem.

Theorem 8. Let q ∈ nω(1) be any prime. The language Non-3-Colorability is in dStatZK [O(n) , O(log q) , C[O(1) , O(n log q)]] . Before proving Theorem 8, we prove that Non-k-Colorability problem can be reduced to a Sumcheck instance. Lemma 1. Given an instance (G, I), where n = |V (G)| and m = |E(G)|, there exists a polynomial PG : {0, 1}N → {0, 1} such that X G is not k colorable ⇐⇒ PG (x) = 0, x∈{0,1}N

where N is O(n + m). Proof. Consider the classical reduction of Non-k-Colorability to k-SAT: Given a graph G = (V, E) with n vertices and m edges, consider the following k-CNF formula ϕ(G) defined as follows. • Variables of ϕ(G): For each node v ∈ V the formula ϕ has k variables c1v , . . . , ckv (one for each color). • Clauses of ϕ(G): The formula ϕ(G) consists of two types of clauses: 1. Color Selection Constraints for each vertex v: _

civ

∧

i∈[k]

i̸=j,i,j∈[k]

| {z }

at least one color

(¬civ ∨ ¬cjv ) {z

(at most one color)

}

2. Adjacency Constraints for each edge (u, v) ∈ E: ^ (¬civ ∨ ¬cjv ) i,j∈[k],i̸=j

By construction of ϕ(G) from the graph G, the following known fact holds. Fact 9. G is k-colorable iff ϕ(G) is satisfiable. The formula ϕ has N = k · n variables and M = (k + 1) · n + k · m clauses. Given such a k-CNF formula ϕ with M clauses over N variables, we construct a multivariate polynomial PG : {0, 1}N → {0, 1} such that: PG (x1 , . . . , xN ) = 1 ⇐⇒ ϕ is satisfied by assignment x1 , . . . , xN where x ∈ {0, 1}N is a possible evaluation of the k · n variables {civ }v∈V,i∈[k] . The polynomial PG is constructed as the usual arithmetization of the formula ϕ. • For each edge e = (u, v) ∈ E with id(u) < id(v) and color i ∈ [k], define the polynomial Wei (ciu , civ ) := 1 − ciu civ . and then the polynomial T (x) : {0, 1}N → {0, 1} given by T (x) :=

Wei (ciu , civ )

i∈[k] e=uv∈E

Where x ∈ {0, 1}N contains the N variables of the form civ for all v ∈ V and i ∈ [k]. 32

• For each vertex v ∈ V , define the polynomials Av , Bv : {0, 1}k → {0, 1} as Y Y (1 − civ cjv ). (1 − civ ), and Bv : (c1v , . . . , ckv ) = Av (c1v , . . . , ckv ) := 1 − i,j∈[k],i<j

i∈[k]

and the polynomial S : {0, 1}N → {0, 1} as Y S(x) := Av (c1v , . . . , ckv ) · Bv (c1v , . . . , ckv ). v∈V

Finally, defining the polynomial PG (x) : {0, 1}N → {0, 1} as PG (x) := T (x) · S(x) yields the following claim, which concludes the proof. Claim 1. The graph G is not k-colorable iff X

PG (x) = 0

x∈{0,1}N

Proof of Claim 1. Direct from Theorem 7, since each evaluation PG (x) for a vector x ∈ {0, 1}N correspond to the evaluation ϕ(x) and this formula is satisfiable iff x is a k-coloring of the graph.

Given this derivation, we proceed to prove Theorem 8. Proof of Theorem 8. Let G = (V, E) by an n-node graph, and consider the polynomial PG given by Lemma 1. We can employ the Sumcheck protocol to verify the absence of a satisfying assignment, i.e., whether: X PG (x) = 0. x∈{0,1}N

P In order to use Theorem 1, we need that the addition x∈{0,1}N PG (x) is at most a value k = O(poly(n))6 since otherwise cannot be encoded in O(log n), but at this point the sum of PG can be as large as 2Ω(n) . Therefore, in the Sumcheck protocol for the polynomial PG , we have to assume a field Fq of size q = Ω(2n ) to ensure X X PG (x) = 0 ⇔ PG (x) = 0 mod q. (16) x∈{0,1}N

x∈{0,1}N

This would violate our O(log n) message size constraint. To address this issue, we proceed as follows: instead of selecting a prime q of exponential size in n, we choose a prime q uniformly at random from the interval [R, 2R], where R = poly(n), and apply the Prime Number Theorem. Theorem 10 (Prime Number Theorem). Let π(x) denote the prime-counting function, i.e., the number of primes less than or equal to x. Then π(x) ∼ 6

x log x

In no-instances, the sum can be very large

as x → ∞

By the Prime Number Theorem, the interval [R, 2R] contains Θ logRR primes. Furthermore, since X PG (x) ≤ 2N , x∈{0,1}N

it can have at most O(N ) distinct prime factors. Combining these two facts, we obtain   X 1 N Pq  q divides PG (x)  ≤ Θ ≤ . R/ log R poly(n) N x∈{0,1}

Therefore, condition (16) holds with high probability over the random choice of q, and representing each field element in Fq requires only O(log n) bits (rather than poly(n) bits). Then we conclude by Theorem 1, since verifying whether a graph is in Non-k-Colorabilityis equivalent to checking whether Equation (16) holds in the Sumcheck-instance (G, PG , q, 0), and replacing the oracle access by the following distributed oracle PG . Distributed oracle access to PG . The oracle access is defined as follows. Given inputs x = x1 , . . . , xN , each node can locally compute the polynomial S(x) without interaction with its neighbors. Then, it only remains to specify how the value T (x) will be computed. Given x, each node u can compute locally the following part of T (x) : Y Y Tu (x) := Wei (x) e=(u,v)∈E i∈[k] v∈Tu , id(u)<id(v)

and it can forward it to its parent in the spanning tree. Then, for each child v sending the value Tv (x), node u verifies the following consistency condition: Y Y Y Tu (x) = Tv (x) · Wei v∈Child(u)

e=(u,v)∈E i∈[k] v∈N (u), id(u)<id(v)

Therefore, at the end of this computation, if u is the root node of the spanning tree, Tu is equivalent to T (x1 , . . . , xN ). Since S(x1 , . . . , xN ) can be computed locally by u, the root node can compute PG (x1 , . . . , xN ). Statistical simulator. Each node v ∈ V throughout the protocol receives two kind of messages: • The messages given by the prover in Steps 1. and 2. of Sumcheck protocol, which by definition are all of them uniform random variables of some known (for node v) set. • The messages Tu (x) given by each child u of the node v, as specified in the distributed oracle access to polynomial PG . And all the information learned by node v is either these messages themselves or some function of these messages. To conclude, we prove that the evaluation of the polynomial PG (x) := T (x) · S(x) at a randomly chosen point (as described by the above distributed oracle) is statistically indistinguishable from the uniform distribution and therefore the oracle query can be replaced with an uniform random value. To this end, observe that the vertex factor S(x) can be determined without any information, and therefore each node can locally simulate uniform random variables and evaluate them in its S(x). The following lemma shows that the evaluation of each Tv (x) can be replaced with an uniform random value in the simulator, as in fact we prove that the complete polynomial T (x) is statistically indistinguishable from the uniform distribution. 34

Lemma 2. Let G = (V, E) be a graph with n = |V |, m = |E| and an integer k. Draw independently c1v , . . . , ckv ∼ Unif(Fq ) for each node v ∈ V . Consider the product of edge-factors T appear in the polynomial PG above. Then 2 n . TV (T, Unif(Fq )) ≤ O q Proof of Lemma 2. Lets define P (0) := T and for each i = 1, ..., L = k · m, we replace the i-th factor of P (i−1) by a new variable Ui ∼ Unif(Fq ) and call it P (i) . Notice that the factors of L Y i.i.d. (L) T are of the form 1 − xy for two random variables x, y ∼ Unif(Fq ) and P = Ui with i=1 i.i.d.

Ui ∼ Unif(Fq ) for all i ∈ [L]. For a given P (i) , let G := 1 − xy be the factor of P (i) which will be replaced by Ui ∼ Unif(Fq ) in P (i+1) . Let RG be the product of remaining factors of P (i) containing x or y, and Rind be the product of factors that are independent of G. Then, P (i) = G·RG ·Rind and P (i+1) = Ui ·RG ·Rind . By Property 2, since Rind is independent of G · RG and Ui · RG , TV P (i) , P (i+1) = TV (G · RG · Rind , Ui · RG · Rind ) ≤ TV (G · RG , Ui · RG ) .

(17)

Therefore we focus on TV (G · RG , Ui · RG ). First, observe that a direct calculation shows that TV (G, Unif(Fq )) = q−1 ∈ O(1/q). Thus, if there is no factor corresponding to RG (the q2 case where all factors in P (i) is independent from x and y), we can bound TV P (i) , P (i+1) = O(() 1/q). We thus assume that there is a factor corresponding to RG . Without loss of generality, we assume that x = c1u and and y = c1v (the other k−1 where (x, y) = (cju , cjv ) for some j ∈ [k]\{1} are analogous). For any s, t ∈ F, let Es,t be the event such that c1u = s and c1v = t. Then, using Property 3 we have TV P (i) , P (i+1) ) ≤ TV (G · RG , Ui · RG ) X = P [Es,t ] · TV ((1 − st) · RG |Es,t , Ui · RG |Es,t ) s,t∈Fq

≤

P [Es,t ] · TV ((1 − st) · RG |Es,t , Ui · RG |Es,t ) + P [ru rv ∈ {0, 1}] .

st∈{0,1} /

(18) Notice that each factor appearing in RG is either 1 1 1 1 • Lu,v w : = (1 − cu cw )(1 − cv cw ) for each w ∈ N (u) ∩ N (v),

• Luw : = (1 − c1u c1w ) for each w ∈ N (u)\N (v), or • Lvw : = (1 − c1v c1w ) for each w ∈ N (v)\N (u), and RG is the product of these O(n) factors. When c1u = s and c1v = t such that s · t ∈ / {0, 1}, both Luw and Lvw are exactly uniform random variables, and for each w ∈ N (u) Q ∩ N (v), the u,v probability that Lu,v w = 0 is at most O(1/q). By union bound, the probability that w Lw ̸= 0

is at least 1 − O(n/q). Moreover, both Luw and Lvw are independently uniform, when ru = s and rv = t such that st ∈ / {0, 1}. Thus, by Property 2, " # " # Y Y u,v u,v TV (RG |Es,t , Unif(Fq )) ≤ P Lw ̸= 0 · TV (RG |Es,t , Unif(Fq )) + P Lw = 0 w

n n n ·O +O ≤ 1−O q q q n =O q for every s, t such that s · t ∈ / {0, 1}. Again by Property 2, TV ((1 − st) · RG |Es,t , Ui · RG |Es,t ) ≤ TV ((1 − st) · RG |Es,t , (1 − st) · Unif(Fq )) + TV ((1 − st) · Unif(Fq ), Ui · Unif(Fq )) + TV (Ui · Unif(Fq ), Ui · RG |Es,t ) = O(n/q) + O(1/q) + O(n/q) = O(n/q) . We also have that for fixed s and t, P [Es,t ] = O 1/q 2 and P c1u · c1v ∈ {0, 1} = O(1/q). Together with Equation (18), we get TV P (i) , P (i+1) ) = O (1/q) assuming q = nω(1) . Now using the triangle inequality and Property 2, the bias of edge factors T is bounded as follows. TV (T, Unif(Fq )) ≤ TV P (0) , P (L) + TV P (L) , Unif(Fq ) (19) ≤

L X

TV P (i−1) , P (i) + TV P (L) , Unif(Fq )

(20)

i=1

2 L L n ≤O +O =O . q q q

(21)

Moreover, since the node v computes some portion Tv (x) of the polynomial T (x) using the messages given by the prover and its neighbors (Tv (x) can be obtained by eliminating some factors from T (x)), the same argument works for the distribution of Tv (x), showing each Tv (x) is also statistically close to uniform. Overall, the constant round simulator just needs to generate enough uniform random variables for each node, since all the information received by each node is either an uniform random variable itself, o it is statistically indistinguishable from uniform distribution (the messages Tv ) given Lemma 2. Together with Theorem 1, this concludes the proof of Theorem 8.

4.2

Counting Subgraphs.

In this section, we study the problem subgraph-counting(H). The formal definition of the problem is below. For this problem, we show the following result, which is a formalization of Theorem 4.

Protocol 4.2: subgraph-counting(H) Input. An n-node graph G = (V, E), with unique identifiers {0, . . . , n − 1}. Each node knows a k-node pattern graph H, the number ∆ < nk , and the ID of its parent in an arbitrary spanning tree rooted at node with ID 0. Decision problem: Decide if the number of copies of H in G is exactly ∆ or not.

Theorem 11. The language subgraph-counting(H) is in dStatZK [O(k log n) , O(log q) , C[O(1) , O(log q)]] where q is any prime such that q ∈ nω(1) for k ∈ O(1) and q > nk for k ∈ ω(1). Proof of Theorem 11. Given a graph G = (V, E), let A : {0, 1}log n × {0, 1}log n → {0, 1} be the adjacency matrix of G as a function, i.e., A(i, j) = 1 ⇐⇒ {i, j} ∈ E and A(i, j) = 0 otherwise. For a given H = (V (H), E(H)), the number of H’s ∆ is represented as X Y A(vi , vj ), (22) Aut(H) · ∆ = v1 ,...,vk ∈{0,1}log n (vi ,vj )∈E(H)

where Aut(H) is the number of automorphisms of H. When dealing with induced copies, the representation also includes the non-edge factors Y X Y Aut(H) · ∆ = A(vi , vj ) (1 − A(vi , vj )) . v1 ,...,vk ∈{0,1}log n (vi ,vj )∈E(H)

(vi ,vj )∈E(H) /

e : F2q log n → We will check the right-hand side of the equation using the Sumcheck protocol. Let A Fq be the multilinear extension of A, i.e., X e y) = A(z, w) · χx,y (z, w), A(x, z,w∈{0,1}log n

where χx,y is a polynomial defined as follows (xℓ is the ℓ-th element of the |Fq |-ary representation n of x ∈ Flog ): q Y χx,y (z, w) = [xℓ · zℓ + (1 − xℓ ) · (1 − zℓ )] · [yℓ · wℓ + (1 − yℓ ) · (1 − wℓ )] . ℓ∈{1,...,log n}

For simplicity, we only focus on the case of k-cliques. For all (induced) subgraphs, the protocol and the analysis are essentially identical to this case7 . Therefore, we let f (v1 , . . . , vk ) = Q e degree O(k 2 log n). Taking i̸=j A(vi , vj ). Then f is a N = k log n-variate polynomial of total n |Fq | to be a prime q > 2nk (note that the number of H’s is at most ≤ nk ), the condition (22) k is equivalent to X k! · ∆ = f (v1 . . . . , vk ), v1 ,...,vk ∈{0,1}log n

since f (v1 , . . . , vk ) coincides with i̸=j A(vi , vj ) for all v1 , . . . , vk ∈ {0, 1}log n . In order to conclude Theorem 4 from Theorem 1, it remains only to show how the nodes can evaluate f at a single point, and that the view of each node is statistically close to the uniform distribution. Q

7 We rely on the fact that f is a product of multilinear polynomials which holds for not only cliques but also all subgraphs.

Oracle access to f . Let (r1 , . . . , rN ) ∈ FN q be any point. Then, f (r1 , . . . , rN ) is a product of 2 e e at O(k ) terms of the multilinear extension A, meaning that it is sufficient if we can compute A ⌈log n⌉ ∗ ∗ a random point. By definition, for any vi , vj ∈ Fq , we have e i∗ , vj∗ ) = A(v

A(vi , vj ) · χvi∗ ,vj∗ (vi , vj ),

vi ∈{0,1}log n vj ∈{0,1}log n

and for each fixed vi , the inner sum can be computed locally by node vi . By summing up the n⌉ e ∗ , v ∗ ) for given v ∗ , v ∗ ∈ F⌈log tree (with the help of the prover), the root node can compute A(v . q i j i j Finally, to conclude it only remains to prove that the polynomial f associated with subgraphcounting(H) is statistically indistinguishable from the uniform distribution when evaluated on a random point. To this end, we show that for all multilinear polynomials, its distribution is statistically close to the uniform distribution when evaluated on a random point. In specific, we prove the following. ev the random variable Lemma 3. Given a graph G = (V, E), for each node v ∈ V define as A ∗ ∗ e representing the portion of A(vi , vj ) that node v receives after summing-up through its subtree. Then, if U ∼ Unif(Fq ), it holds that s ! log n ev , U ≤ O TV A q Proof of Lemma 3. We use the following standard Fourier analysis technique. Lemma 4 (Parseval’s theorem). For any f : Fq → C define the Fourier transform fb(λ) := P 2πit/q for t ∈ F . Then q a∈Fq f (a)ψ(λa), where ψ(t) = e X

|f (a)|2 =

a∈Fq

1 X b 2 |f (λ)| . q λ∈Fq

ev . Let δ(a) := P [Q(x) = a] − 1 be the bias of Q on Let v ∈ V be any node and fix Q := A q x∈FN q 1P a ∈ Fq . We write TV := 2 a∈Fq |δ(a)| the total variation distance between Q and the uniform distribution. The Fourier transform of δ is given by X b δ(λ) := δ(a)ψ(λa) a∈Fq

1 = P [Q(x) = a] − · ψ(λa) x q a 1X = Ex∈FN ψ λQ(x) − ψ(λa) q q a = Ex∈FN ψ λQ(x) q b for λ ∈ F× q , and δ(0) = 0.

Next, we let ⃗δ be the q-dimensional vector where the a-th element is |δ(a)| and ⃗1 be the all-one vector. By Cauchy-Schwarz we have X |δ(a)| = ⃗δ · ⃗1 a∈Fq

≤ ∥⃗1∥2 · ∥⃗δ∥2 s X √ = q· |δ(a)|2 .

(23)

Hence, combined with Parseval’s theorem (Lemma 4), the total variation distance is now bounded by √ sX q 1X |δ(a)| ≤ |δ(a)|2 TV = 2 a 2 a √ s X q 1 2. b = |δ(λ)| 2 q λ̸=0

b Our goal is to derive an explicit universal bound on the absolute Fourier coefficients |δ(λ)|. Lemma 5. Assume that for some i, Q(x1 , . . . , xN ) = xi h(x̸=i ) + R(x̸=i ) with h ̸≡ 0 multilinear. Then for every λ ∈ F× q N −1 b |δ(λ)| ≤ . q Proof. Without loss of generality, assume that P (x1 , . . . , xN ) = x1 h(x2 , . . . , xN )+R(x2 , . . . , xN ) b with h ̸≡ 0 multilinear. δ(λ) can be written as b δ(λ) = Ex1 ,...,xN ψ λP (x1 , . . . , xN ) i h X ψ λx1 h(x2 , . . . , xN ) . = Ex2 ,...,xN ψ λR(x2 , . . . , xN ) 1q x1 ∈Fq

For fixed α := h(x2 , . . . , xN ) the inner sum equals ( 1 1X ψ(λαx1 ) = q x 0 1

(α = 0), (α ̸= 0),

by orthogonality of roots of unity. Since h involves at most N − 1 variables and each with degree 1, Schwartz-Zippel gives

b |δ(λ)| ≤ ≤

x2 ,...,xN

h(x2 , . . . , xN ) = 0

N −1 . q

Recall that for the multilinear extension of the adjacency matrix, there exists at least one variable xi satisfying the assumption of the above lemma: Q(x1 , . . . , xN ) = xi h(x̸=i ) + R(x̸=i ) with h ̸≡ 0 multilinear (otherwise, the corresponding graph cannot have any edges). We now get the upper bound for TV: √ s q (N − 1)2 log n 1 TV ≤ · · (q − 1) ≤ O . √ 2 q q2 q

Reducing Round Complexity by Divide-and-Conquer Sumcheck

In this section, we improve the round complexity of subgraph counting using the recent technique of [LMN25]. For k ∈ O(1), this reduces the round complexity from O(log n) to O(log log n). We prove the following theorem. Theorem 12 (Restatement of Theorem 4). The language subgraph-counting(H) is in 2 log q dStatZK O(k log k + log log n) , O + k log k log q , C[O(1) , k · polylog(n, k)] log k where q is any prime such that q ∈ nω(1) for k ∈ O(1) and q > nk for k ∈ ω(1). In order to prove this result, we use the following protocol which we call Fold-DCSF,a [LMN25]. Fold-DCSF,a . m Assumption: Both players have oracle access to a polynomial F : FN q → Fq where N = 2 .

• Commit phase: For i ∈ {1, . . . , m} do the following: P (i) Define 2m−i -variate polynomial F0 (x) = ⃗a∈{0,1}2m−i F (i−1) (x, ⃗a). The verifier indepenand z (i) ∈R Fq uniformly at random, and sends them to the dently samples α(i) ∈R Fm−i q prover. The prover and the verifier set the following polynomials and value. (i)

– F1 = F (i−1) (α(i) , ·) (i)

(i)

– F (i) = z (i) F0 + F1

(i)

– a(i) = z (i) a(i−1) + F0 (α(i) ) • Query phase: The verifier computes a(m) =

m Y j=1

z (j) a +

m X



m Y

 j=1

(j)

by querying F0 (α(j) ) for j ∈ {1, . . . , m}.

ℓ=j+1

 (j)

z (ℓ)  F0 (α(j) )

The verifier picks β ∈ F uniform randomly and checks F (m) (β) = F (α(1) , . . . , α(m) , β) +

m X

(j)

z (j) F0 (α(j+1) , . . . , α(m) , β)

j=1 (j)

by querying F (m) (β), F (α(1) , . . . , α(m) , β), and F0 (α(j+1) , . . . , α(m) , β) for j ∈ {1, . . . , m}.

The protocol is originally implemented in the interactive oracle proof model where each message from the prover is a function which can be queried by the verifier. In the commit phase (j) of Fold-DCSF,a , the verifier receives oracle access to F (m) and F0 for j ∈ {1, . . . , m}, and in the query phase the verifier makes 2m + 2 oracle queries. The following analysis is used in our proof. P Proposition 2 (Completeness and soundoness of Fold-DCSF,a , from [LMN25]). If F = a, then given an honest prover described in the protocol Fold-DCSF,a , the verifier accepts with probability 1, Otherwise, the verifier accepts with probability at most (m + 1)(d + 1) , |Fq | where d is the total degree of F .

5.1

Splitting the instance

Let us consider the N -variate polynomial f associated with subgraph-counting(H), and let n ℓ = ⌊ log log k ⌋. We define a protocol Psplit for subgraph-counting(H) based on splitting the Sumcheck relation, in which the honest prover and the verifier proceed as follows. Psplit . 1. The prover sends X

h1 (x1 , . . . , xℓ ) =

f (x1 , . . . , xℓ , a).

a∈{0,1}N −ℓ

2. Let t be a positive integer that will be determined later. For i ∈ {1, . . . , t − 1}, both do the following. (a) The verifier picks α(i) ∈ Fℓ . Both set e hi (x1 , . . . , xN −iℓ ) = e hi−1 (α(i) , x1 , . . . , xN −iℓ ) (where e h0 = f ). The verifier computes ai = hi (α(i) ) by querying to hi . (b) The prover sends X

hi+1 (x1 , . . . , xℓ ) =

e hi (x1 , . . . , xℓ , a).

a∈{0,1}N −(i+1)ℓ

3. The verifier picks α(t) ∈ Fℓ . The prover sends e ht (x1 , . . . , xN −tℓ ) = e ht−1 (α(t) , x1 , . . . , xN −tℓ ). (t) N −tℓ Both set at = ht (α ). The verifier picks β ∈ F , and checks h̃t (β) = f (α(1) , . . . , α(t) , β) by querying to h̃t and f . 4. The prover and the verifier jointly solve Fold-DCSh1 ,a , Fold-DCShi+1 ,ai for i ∈ {1, . . . , t − 1}, Fold-DCSeht ,at in parallel.

For this protocol, we prove the following. P Proposition 3 (Completeness). If f = a, then given h1 , . . . , ht , e ht by the honest prover of Psplit , the verifier accepts with probability 1. P Proof. Assume that x1 ,...,xN f (x1 , . . . , xN ) = a. The verifier accepts Fold-DCSh1 ,a since X

h1 (x1 , . . . , xℓ ) =

f (x1 , . . . , xN ) = a.

x1 ,...,xN

x1 ,...,xℓ

For i ∈ {1, . . . , t − 1}, the verifier accepts Fold-DCShi+1 ,Si since X X X e hi (x1 , . . . , xℓ , a) hi+1 (x1 , . . . , xℓ ) = x1 ,...,xℓ a∈{0,1}N −(i+1)ℓ

x1 ,...,xℓ

e hi−1 (α(i) , x1 , . . . , xN −iℓ )

x1 ,...,xN −iℓ

= hi (α(i) ). The verifier accepts Fold-DCSeht ,at since X

e ht (x1 , . . . , xN −tℓ ) =

x1 ,...,xN −tℓ

e ht−1 (α(t) , x1 , . . . , xN −(t−1)ℓ )

x1 ,...,xN −tℓ

= ht (α(t) ). Finally, it holds h̃t (β) = f (α(1) , . . . , α(t) , β) for any β ∈ FN −tℓ as h̃t (x) ≡ F (α(1) , . . . , α(t) , x). Proposition 4 (Soundness). If

f ̸= a, then for any prover of Psplit , the verifier accepts with

td log N |Fq |

, where d is the total degree of f . probability at most O P Proof. Assume that f ̸= a. Let pi for i ∈ {1. . . . , t}, pet be the polynomial actually sent by the prover. Then, ai = pi (α(i) ) for i ∈ {1, . . . , t}. We write Fold-DCSi = Fold-DCSpi ,ai−1 for i ∈ {1, . . . , t} and Fold-DCSt+1 = Fold-DCSpet ,at . Define the following events: Eacc is the event that the verifier accepts. Ei is the event pi = hi P e for i ∈ {1, . . . , t}, and EP is the event p e = h . F is the event p = a t+1 t t Vi i i−1 for i ∈ {1, . . . , t}, pet = at . Define Fall = Fi . Due to the soundness of Fold-DCS, for and Ft+1 is the event i

i ∈ {1, . . . , t + 1}, Pr The verifier accepts Fold-DCSi Fi ≤ O

d log N |Fq |

By union bound, t+1 X Pr Eacc Fall ≤ Pr Eacc Fi i=1

≤

t+1 X

Pr The verifier accepts Fold-DCSi Fi ≤ O

i=1

td log N |Fq |

Next, we assume Fall holds. Then, from the assumption that Pr E1 Fall = 1.

f ̸= a, we have

Under E1 ∧ F2 , p1 ̸≡ h1 and hence p1 (α(1) ) = h1 (α(1) ) with probability at most d/|Fq |, implying E2 holds with probability at least 1 − d/|Fq |. Therefore, Pr E2 Fall = Pr E2 Fall ∧ E1 · Pr E1 Fall ≥ 1 − d/|Fq |. Similarly, for i ∈ {2, . . . , t}, under Ei ∧ Fi+1 , we have pi (α(i) ) = hi (α(i) ) with probability at most d/|Fq |, implying Ei+1 holds with probability at least 1 − d/|Fq |. Therefore, id Pr Ei+1 Fall ≥ Pr Ei+1 Fall ∧ Ei · Pr Ei Fall ≥ 1 − . |Fq | Now, under Et+1 , p̃t (β) = f (α(1) , . . . , α(t) , β) holds with probability at most D/|F|. Therefore, we have h i Pr [Eacc |Fall ] ≤ Pr p̃t (β) = f (α(1) , . . . , α(t) , β) Fall h i ≤ Pr p̃t (β) = f (α(1) , . . . , α(t) , β) Fall ∧ Et+1 · Pr Et+1 Fall + Pr [Et+1 |Fall ] d td td ≤ · 1− + |Fq | |Fq | |Fq | (t + 1)d ≤ . |Fq | The acceptance probability is bounded by

Pr [Eacc ] = Pr [Eacc |Fall ] + Pr Eacc Fall = O

5.2

td log N |Fq |

Proof of Theorem 12

Propositions 3 and 4 show that Psplit correctly solves subgraph-counting(H). We next explain how to implement oracle access to the polynomials appeared in Psplit . Implementing oracle access to the polynomials. For subgraph-counting(H), we use N = k⌈log n⌉ since Y e i , vj ). f (v1 , . . . , vk ) = A(v i̸=j

e j) is a multilinear polynomial. So f has We also set t = k⌈log k⌉ in Psplit . Observe that A(i, e individual degree k−1. Each of h1 , . . . , ht , ht can be obtained by taking sums of f or substituting random values to f . Thus, they also have individual degree k − 1, implying that the number of ⌊ log n ⌋

monomials in each of them is at most k ℓ = k log k ≤ n (here we used the fact that the number of variables in e ht is N − tℓ ≤ ℓ). The prover can distribute the coefficient of a single monomial to each node, with a vector from {0, 1, . . . , k − 1}ℓ representing the corresponding monomial (the i-th element of the vector represents the degree of the i-th variable). To implement queries, the prover gives each node the partial sums of monomials assigned to all its descendants in the spanning tree, and the root node can compute the value by aggregating them along the tree. In all of instances of Fold-DCS, polynomials sent by the prover have at most n monomials as well, and therefore oracle access to these polynomials can be implemented in exactly the same way. 43

Analysis of complexities. The first three steps of Psplit require t = O(k log k) rounds and 2 q ℓq ∈ O( log log k )-bit messages. The last step (Step (4)) requires O(log ℓ) = O(log log n) rounds and O(t log q) = O(k log q log k)-bit messages. The simulator for this protocol simulates each oracle query by an uniform random value. Recall that all polynomials defined in the protocol Psplit are also multilinear. Thus, the Fourier analysis given in Lemma 3 shows that the evaluation of these polynomials at random points are statistically close to the uniform distribution. For the first three steps of Psplit , the simulator can be taken from the class C[O(1), O(k log2 q)]. For the last step, recalling that the protocol Fold-DCSF,a for N variables requires O(log N ) rounds and O(log N log q)-bit messages, it can be simulated by the class C[O(1), O(t log2 ℓ log q)]. The resulting simulator can be taken from the class C[O(1), k · polylog(n, k)], which completes the proof of Theorem 12.

A Barrier for Round Reduction for Non-k-Colorability

In this section, we again deal with Non-k-Colorability, focusing on constant-degree graphs. In Section 6.1, we prove the upper bound side of Theorem 5, and in Section 6.2, we prove the lower bound side of Theorem 5.

6.1

Upper Bound for Constant-Degree Graphs

Consider the task of verifying Non-k-Colorability of constant-degree graphs. We use the polynomial f for Non-k-Colorability, i.e., N = O(n) (for constant integer k). We run the first three steps of Psplit in Section 5.1, using t the minimum integer such that N − tℓ ≤ ℓ where ℓ = ⌈log3 n⌉, to generate t + 1 instances of Sumcheck. Instead of running Fold-DCS as in the final step of Psplit , the prover and the verifier perform the standard Sumcheck (using our Sumcheck compiler) for the generated instances. This solves Non-3-Colorability of constant-degree graphs. Analysis. Generating t + 1 instances by the first three steps of Psplit takes O(t) ∈ O(n/ log n) rounds and O(log2+o(1) n)-bit messages per node per round. Running t + 1 instances of Sumcheck requires the same amount of rounds and message size: Consider that the prover and the verifier check O(log n) Sumcheck instances at once, using O(log n) rounds and O(log2+o(1) n)-bit messages per node per round. This is repeated for O(t/ log n) = O(n/ log2 n) times, making the total round complexity O(n/ log n). The completeness and soundness follow from Proposition 3 and Proposition 4. But here the total degree in the soundness error is replaced by the individual degree, which is O(1), as we use the standard Sumcheck in this case.

6.2

Conditional Lower Bound for Constant-Degree Graphs

Now we show a lower bound for Non-3-Colorability problem for simplicity. The same reduction holds for any Non-k-Colorability problem for fixed k. We will use the following lemmas. Lemma 6 (The Sparsification Lemma [IPZ01]). For all ε ≥ 0, k-CNF F on n variables can be written as the disjunction of at most 2εn k-CNFs {Fi } on n variables such that Fi contains each variable in at most poly(1/ε) clauses. Moreover, this reduction takes at most poly(n)2εn time. Let AM[b, M ] be the class of languages that can be decided by AM protocols in which the prover and the verifier exchange at most b bits in total, and the number of messages exchanged

between the prover and the verifier is M . Let AMTIME[T ] be the class of languages that can be decided by 2-round AM protocols in which the prover and the verifier send each at most T bits, and the runtime of the verifier is at most T . The following round reduction lemma for Arthur-Merlin protocols is shown in [GVW02]. Lemma 7 ([GVW02]). AM[b, M ] ⊆ AMTIME[(b · M )O(M ) ]. We are now ready to prove the following theorem. Theorem 13. Let Π be the problem of certifying Non-3-Colorability of constant degree graphs. Assuming coNP ̸⊆ AMTIME[2o(n) ], for any b, M > 0 satisfying b = poly(n) and M ∈ o(n/ log n), there is no M -round and b-message distributed Arthur-Merlin protocol for Π where the verification algorithm at each node is a polynomial-time algorithm. Proof. Let Φ be a 3-CNF on variables x1 , . . . , xn . Fix arbitrary ε > 0. By Lemma 6, in 2O(εn) time, we can construct 2εn 3-CNFs {ϕj }j∈[2εn ] such that each CNF ϕj contains m = O(n) clauses such that each variable xi appears at most poly(1/ε) = O(1) clauses. Fix arbitrary CNF ϕ in these 2εn 3-CNF formulas. The standard reduction from 3-SAT to 3-coloring. Let ϕ be a 3-CNF formula on n variables, where each variable appears at most ∆ clauses for some constant ∆. We follow the standard reduction from 3-SAT to 3-coloring (e.g., [Gol08]). The constructed graph Gϕ has three special nodes vT , vF , vB which form a triangle. For each variable xi , we have two nodes v(xi ), v(xi ). We have an edge connects them, and they are also connected to vB . For each clause C, we create a clause gadget, as illustrated in Figure 1. A clause gadget for a clause C = (xi ∨ xj ∨ xk ) contains six nodes where v(xi ), v(xj ), v(xk ), vF , vB are connected to these gadget nodes.

Figure 1: Clause gadget for a clause C = (xi ∨ xj ∨ xk ). In any valid 3-coloring, at least one of v(xi ), v(xj ), v(xk ) has the same color as of vT . Note that all of v(xi ), v(xj ), v(xk ) are connected to vB (but the corresponding edges are omitted in the figure for simplicity).

Reducing the maximum degree of the graph. In the above construction, the number of nodes is O(n + m) where m is the number of clauses in ϕ. Since we assumed that each variable appears at most constant number of clauses, m ∈ O(n). In the constructed graph, variable nodes and gadget nodes have constant degrees, but the degree of vT , vF , vB are at least Ω(n). We can reduce the maximum degree as follows. Let us focus on one node, e.g., vB . We add a binary tree rooted at vB of depth O(log(deg(vB ))), where the number of leaves is exactly equal 45

to deg(vB ). We delete each incident edge of vB , and add a new edge connected to an unused leaf node instead of the original vB . Finally, we replace each tree edge by another gadget as illustrated in Figure 2, to make all tree nodes have the same color. This modification increases

Figure 2: A gadget for a tree edge (u, v). In any valid 3-coloring, u and v must have the same color. the total number of nodes to O(n log n) while ensuring maximum degree O(1). For a given 3-SAT formula ϕ, we construct Gϕ in poly(n) time. Assume that Non-3Colorability can be certified by an m-round dAM protocol with message size b on constantdegree, n-node and m-edge graphs. Recall that Gϕ is a O(n log n)-node O(n log n)-edge graph. The verification algorithm A of this dAM protocol is a poly-time algorithm. Thus, simulating the verification algorithm A of all nodes gives an AM[b′ , m] protocol for some b′ = poly(n). Using Lemma 7, this can be converted to an AMTIME[2o(n) ] protocol, as ′

(b · m)

O(m)

= poly(n)

n log n

= 2o(n) .

Running the converted protocol for 2εn different instances (created by Lemma 6) solves Unsat from the construction of Gϕ . This implies that for any ε > 0, we have Unsat ∈ AMTIME[2εn · 2o(n) · nO(1) ] for any ε > 0, implying Unsat ∈ AMTIME[2o(n) ].

Conclusion

In this work, based on the robust Sumcheck protocol, we introduce a general framework for studying classical hard problems in distributed verification under a statistical zero-knowledge guarantee. Using this framework, we improve the state of the art for two central problems— Non-k-Colorability and subgraph-counting(H). Our results leave open the problem of understanding the scope of our Sumcheck-based approach. In our application to Non-k-Colorability, the reduction from k-coloring to k-SAT preserves the relevant locality: the resulting constraints are associated with vertices and edges, and the corresponding arithmetization can be evaluated by local computation plus aggregation. It would be interesting to develop a more systematic theory of such locality-preserving reductions between distributed graph problems.8 More generally, one may ask which distributed graph predicates admit a low-degree arithmetization whose terms are locally computable and whose global sum captures the desired property. Such a characterization would clarify a broader class of Sumcheck-friendly distributed problems. Relatedly, our results suggest that round compression is strongly problem-dependent; it remains open to characterize when the round complexity of distributed Sumcheck can be reduced, as in our protocol for subgraph-counting(H). 8

A related notion of reductions has recently been studied in local certification (non-interactive distributed verification model) by Esperet and Zeitoun [EZ25], where local reductions are used to transfer proof-size lower bounds between graph properties. Our question is different, but similar in spirit: we ask which reductions preserve the locality and algebraic structure needed for distributed Sumcheck.

A second direction is to make the framework more black-box. Our general distributed Sumcheck protocol assumes oracle access to the target polynomial, but in concrete graph problems this oracle access must be implemented inside the network, and the resulting transcript must be shown to preserve the statistical zero-knowledge property. In this work, this step is handled separately for Non-k-Colorability and subgraph-counting(H), using problemspecific properties of their arithmetizations. A natural goal is to abstract this part into a general compiler: given a suitable arithmetization of a distributed predicate, can one automatically obtain a distributed statistical zero-knowledge proof with comparable round and message complexity? Such a compiler would be interesting in light of existing compilers for distributed zero-knowledge [BKO22, GPP25]. These results provide broad applicability, but they may incur large proof-size overheads or rely on cryptographic assumptions. A Sumcheck-based compiler could offer a complementary route for problems admitting sufficiently local low-degree arithmetizations. A stronger version of this question is whether such a compiler can achieve perfect zero-knowledge for some nontrivial classes of problems, namely, whether the oracle evaluation part can be simulated exactly rather than only up to small statistical distance. Acknowledgments. The authors are grateful to the anonymous reviewers for their constructive comments and suggestions, which improved the current presentation of this work.

References [ATBC+ 23]

Eden Aldema Tshuva, Elette Boyle, Ran Cohen, Tal Moran, and Rotem Oshman. Locally Verifiable Distributed SNARGs. In Theory of Cryptography: 21st International Conference, TCC 2023, page 65–90, 2023.

[ATO24]

Eden Aldema Tshuva and Rotem Oshman. Fully Local Succinct Distributed Arguments. In 38th International Symposium on Distributed Computing (DISC 2024), volume 319, pages 1:1–1:24, 2024.

[Bab85]

László Babai. Trading group theory for randomness. In Proceedings of the 17th Annual ACM Symposium on Theory of Computing, pages 421–429, Providence, Rhode Island, USA, May 1985. ACM.

[BGK+ 25]

Tatiana Belova, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin, and Denil Sharipov. Polynomial formulations as a barrier for reduction-based hardness proofs. ACM Trans. Algorithms, March 2025. Just Accepted.

[BKO22]

Aviv Bick, Gillat Kol, and Rotem Oshman. Distributed Zero-Knowledge Proofs Over Networks. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2426–2458, 2022.

[BOGG+ 90] Michael Ben-Or, Oded Goldreich, Shafi Goldwasser, Johan Håstad, Joe Kilian, Silvio Micali, and Phillip Rogaway. Everything provable is provable in zeroknowledge. In Advances in Cryptology—CRYPTO’88: Proceedings 8, pages 37–56. Springer, 1990. [BSCF+ 17]

Eli Ben-Sasson, Alessandro Chiesa, Michael A Forbes, Ariel Gabizon, Michael Riabzev, and Nicholas Spooner. Zero knowledge protocols from succinct constraint detection. In Theory of Cryptography: 15th International Conference, TCC 2017, Baltimore, MD, USA, November 12-15, 2017, Proceedings, Part II 15, pages 172– 206. Springer, 2017.

[BSCR+ 19]

Eli Ben-Sasson, Alessandro Chiesa, Michael Riabzev, Nicholas Spooner, Madars Virza, and Nicholas P Ward. Aurora: Transparent succinct arguments for r1cs. In Advances in Cryptology–EUROCRYPT 2019: 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Darmstadt, Germany, May 19–23, 2019, Proceedings, Part I 38, pages 103–128. Springer, 2019.

[CFGS22]

Alessandro Chiesa, Michael A Forbes, Tom Gur, and Nicholas Spooner. Spatial isolation implies zero knowledge even in a quantum world. ACM Journal of the ACM (JACM), 69(2):1–44, 2022.

[CFK+ 15]

Marek Cygan, Fedor V Fomin, Lukasz Kowalik, Daniel Lokshtanov, Daniel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized algorithms, volume 5. Springer, 2015.

[CFP19]

Pierluigi Crescenzi, Pierre Fraigniaud, and Ami Paz. Trade-Offs in Distributed Interactive Proofs. In 33rd International Symposium on Distributed Computing (DISC 2019), pages 13:1–13:17, 2019.

[CFS17]

Alessandro Chiesa, Michael A Forbes, and Nicholas Spooner. A zero knowledge sumcheck and its applications. arXiv preprint arXiv:1704.02086, 2017.

[CGI+ 16]

Marco L Carmosino, Jiawei Gao, Russell Impagliazzo, Ivan Mihajlin, Ramamohan Paturi, and Stefan Schneider. Nondeterministic extensions of the strong exponential time hypothesis and consequences for non-reducibility. In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science (ITCS 2016), pages 261–270, 2016.

[CHPP20]

Keren Censor-Hillel, Ami Paz, and Mor Perry. Approximate proof-labeling schemes. Theoretical Computer Science, 811:112–124, 2020.

[CT06]

Thomas M. Cover and Joy A. Thomas. Elements of Information Theory. Wiley, Hoboken, NJ, 2 edition, 2006.

[Dur19]

Rick Durrett. A Course in Probability Theory. Cambridge University Press, 2019.

[EZ25]

Louis Esperet and Sébastien Zeitoun. Reductions in local certification. In International Workshop on Graph-Theoretic Concepts in Computer Science, pages 192–204. Springer, 2025.

[FLGNP21]

Pierre Fraigniaud, François Le Gall, Harumichi Nishimura, and Ami Paz. Distributed Quantum Proofs for Replicated Data. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021), pages 28–1, 2021.

[FMO+ 19]

Pierre Fraigniaud, Pedro Montealegre, Rotem Oshman, Ivan Rapaport, and Ioan Todinca. On distributed merlin-arthur decision protocols. In International Colloquium on Structural Information and Communication Complexity, pages 230–245. Springer, 2019.

[For87]

Lance Fortnow. The complexity of perfect zero-knowledge. In Proceedings of the nineteenth annual ACM symposium on Theory of computing, pages 204–209, 1987.

[FP23]

Orr Fischer and Merav Parter. Distributed CONGEST algorithms against mobile adversaries. In Rotem Oshman, Alexandre Nolin, Magnús M. Halldórsson, and Alkida Balliu, editors, Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing, PODC 2023, pages 262–273, 2023.

[FPSP19]

Pierre Fraigniaud, Boaz Patt-Shamir, and Mor Perry. Randomized proof-labeling schemes. Distributed Computing, 32:217–234, 2019.

[GKR15]

Shafi Goldwasser, Yael Tauman Kalai, and Guy N Rothblum. Delegating computation: interactive proofs for muggles. Journal of the ACM (JACM), 62(4):1–64, 2015.

[GMR89]

Shafi Goldwasser, Silvio Micali, and Charles Rackoff. The knowledge complexity of interactive proof systems. SIAM J. COMPUT, 18(1):186–208, 1989.

[Gol08]

Oded Goldreich. Computational Complexity: A Conceptual Perspective. Cambridge University Press, 2008.

[GOS24]

Tom Gur, Jack O’Connor, and Nicholas Spooner. Perfect zero-knowledge PCPs for # P. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC 2024), pages 1724–1730, 2024.

[GOS25]

Tom Gur, Jack O’Connor, and Nicholas Spooner. A Zero-Knowledge PCP Theorem. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing (STOC 2025), page 986–994, 2025.

[GP25]

Yuval Gil and Merav Parter. New Distributed Interactive Proofs for Planarity: A Matter of Left and Right. In 39th International Symposium on Distributed Computing (DISC 2025), pages 34:1–34:23, 2025.

[GP26]

Yuval Gil and Merav Parter. Distributed interactive proofs for planarity with logstar communication. In Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 899–924. SIAM, 2026.

[GPP25]

Alex B Grilo, Ami Paz, and Mor Perry. Distributed Non-Interactive ZeroKnowledge Proofs. arXiv preprint arXiv:2502.07594, 2025.

[GS16]

Mika Göös and Jukka Suomela. Locally checkable proofs in distributed computing. Theory of Computing, 12:1–33, 2016.

[GVW02]

Oded Goldreich, Salil Vadhan, and Avi Wigderson. On interactive proofs with a laconic prover. computational complexity, 11:1–53, 2002.

[HKN24]

Atsuya Hasegawa, Srijita Kundu, and Harumichi Nishimura. On the power of quantum distributed proofs. In Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing, pages 220–230, 2024.

[HP21]

Yael Hitron and Merav Parter. Broadcast CONGEST algorithms against adversarial edges. In Seth Gilbert, editor, 35th International Symposium on Distributed Computing, DISC 2021, volume 209, pages 23:1–23:19, 2021.

[HPY23]

Yael Hitron, Merav Parter, and Eylon Yogev. Secure distributed network optimization against eavesdroppers. In Yael Tauman Kalai, editor, 14th Innovations in Theoretical Computer Science Conference, ITCS 2023, volume 251, pages 71:1– 71:20, 2023. 49

[IPZ01]

Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? Journal of Computer and System Sciences, 63(4):512–530, 2001.

[JMMRW26] Benjamin Jauregui, Augusto Modanese, Pedro Montealegre, and Martı́n Rı́osWilson. Strong and hiding distributed certification of bipartiteness, 2026. [JMR22]

Benjamin Jauregui, Pedro Montealegre, and Ivan Rapaport. Distributed interactive proofs for the recognition of some geometric intersection graph classes. In International Colloquium on Structural Information and Communication Complexity, pages 212–233. Springer, 2022.

[KKP10]

Amos Korman, Shay Kutten, and David Peleg. Proof labeling schemes. Distributed Computing, 22:215–233, 2010.

[KOS18]

Gillat Kol, Rotem Oshman, and Raghuvansh R Saxena. Interactive distributed proofs. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, pages 255–264, 2018.

[LFKN92]

Carsten Lund, Lance Fortnow, Howard Karloff, and Noam Nisan. Algebraic methods for interactive proof systems. Journal of the ACM (JACM), 39(4):859–868, 1992.

[LGMN23a] François Le Gall, Masayuki Miyamoto, and Harumichi Nishimura. Distributed Merlin-Arthur Synthesis of Quantum States and Its Applications. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023), pages 63–1, 2023. [LGMN23b] François Le Gall, Masayuki Miyamoto, and Harumichi Nishimura. Distributed Quantum Interactive Proofs. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023), pages 42–1, 2023. [LMN25]

Christophe Levrat, Tanguy Medevielle, and Jade Nardi. A divide-and-conquer sumcheck protocol. IACR Communications in Cryptology, 2(1), 2025.

[MMRW25]

Augusto Modanese, Pedro Montealegre, and Martı́n Rı́os-Wilson. Brief announcement: Strong and hiding distributed certification of k-coloring. In Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC ’25, page 379–382, 2025.

[MRRR21]

Pedro Montealegre, Diego Ramı́rez-Romero, and Ivan Rapaport. Compact distributed interactive proofs for the recognition of cographs and distance-hereditary graphs. In International Symposium on Stabilizing, Safety, and Security of Distributed Systems, pages 395–409. Springer, 2021.

[MRRR25]

Pedro Montealegre, Diego Ramirez-Romero, and Ivan Rapaport. Shared Versus Private Randomness in Distributed Interactive Proofs. Algorithmica, 87(3):377– 404, 2025.

[NPY20]

Moni Naor, Merav Parter, and Eylon Yogev. The power of distributed verifiers in interactive proofs. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1096–115. SIAM, 2020.

[PY19a]

Merav Parter and Eylon Yogev. Distributed Algorithms Made Secure: A Graph Theoretic Approach. In Proceedings of the 2019 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1693–1710, 2019.

[PY19b]

Merav Parter and Eylon Yogev. Secure distributed computing made (nearly) optimal. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, page 107–116, 2019.

[RBO89]

Tal Rabin and Michael Ben-Or. Verifiable secret sharing and multiparty protocols with honest majority. In Proceedings of the Twenty-first Annual ACM Symposium on Theory of Computing (STOC ’89), pages 73–85. ACM, 1989.

[RRR16]

Omer Reingold, Guy N Rothblum, and Ron D Rothblum. Constant-round interactive proofs for delegating computation. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 49–62, 2016.

[Sha79]

Adi Shamir. How to share a secret. Communications of the ACM, 22(11):612–613, 1979.

[Sha92]

Adi Shamir. Ip= pspace. Journal of the ACM (JACM), 39(4):869–877, 1992.

[TV06]

Terence Tao and Van Vu. Additive Combinatorics. Cambridge University Press, 2006.

[Wil16]

Richard Ryan Williams. Strong ETH Breaks With Merlin and Arthur: Short Non-Interactive Proofs of Batch Evaluation. In 31st Conference on Computational Complexity (CCC 2016), 2016.

[XZZ+ 19]

Tiacheng Xie, Jiaheng Zhang, Yupeng Zhang, Charalampos Papamanthou, and Dawn Song. Libra: Succinct zero-knowledge proofs with optimal prover computation. In Advances in Cryptology–CRYPTO 2019: 39th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18–22, 2019, Proceedings, Part III 39, pages 733–764. Springer, 2019.

Record · ID 187288 · SHA-256 ab866ed594650a2b
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.