---
title: "Batch, Pack, and Prove: More Efficient Verifiable Computation for CKKS"
authors: "Ignacio Cascudo, Anamaria Costache, Daniele Cozzo, Dario Fiore, Antonio Guimarães, Eduardo Soria-Vazquez"
venue: "Advances in Cryptology – ASIACRYPT 2026"
source: "arXiv:2611.16922 (official copy)"
source_version: 2026-11-13
canonical: https://antonioguimaraes.org/publications/batch-pack-prove/
pdf: https://arxiv.org/pdf/2611.16922
generator: scripts/fulltext.py (pdftotext)
---

# Batch, Pack, and Prove: More Efficient Verifiable Computation for CKKS

*Ignacio Cascudo, Anamaria Costache, Daniele Cozzo, Dario Fiore, Antonio Guimarães, Eduardo Soria-Vazquez*. Advances in Cryptology – ASIACRYPT 2026.

> Automatic plain-text transcript of the author version, provided for search and AI assistants. Formulas, tables, figures and footnotes are not reproduced faithfully. Read and cite the paper: https://arxiv.org/pdf/2611.16922

<!-- page 1 -->

Batch, Pack, and Prove: More Efficient Verifiable Computation for CKKS

Ignacio Cascudo 1 , Anamaria Costache 2 , Daniele Cozzo 1 , Dario Fiore 1 , Antonio Guimarães 1 , and Eduardo Soria-Vazquez 3

IMDEA Software Institute, Madrid, Spain. École Polytechnique, Paris, France. Technology Innovation Institute, Abu Dhabi, UAE.

Abstract. An important challenge in homomorphic encryption (HE) is ensuring the integrity of the encrypted computations. Although verifiable computation can address this in theory, making it practical is far from trivial. [Cascudo et al. CRYPTO 2025] recently proposed a solution to this problem for the CKKS scheme. In particular, they propose new succinct arguments that efficiently prove arithmetic circuits and range checks over the ring R q = Z q [Y ]/(Y N + 1), and combine them to prove computations on CKKS ciphertexts. Despite the important progress, their work faces scalability challenges: the size of the polynomial commitment proofs, a large O(N ) overhead in range proofs, and the lack of an explicit method for efficient—sublinear in circuit size—verification. In this paper we present new techniques that remove all these bottlenecks. First, we provide a more efficient arithmetization of CKKS computations. Second, we introduce BatchFold, a new polynomial commitment for R q that supports batched evaluations and achieves shorter proofs. Third, we design packing, a novel algebraic technique that eliminates the need to commit to massive polynomials and removes the O(N ) overhead in range proofs. Finally, we introduce SparsePack, an efficient protocol for proving the evaluations of sparse, circuit-dependent polynomials, leveraging both packing and batched evaluations. We evaluate the efficiency of our solution on a generic neural network architecture, achieving proofs several orders of magnitude smaller and faster than prior approaches.

Keywords: Verifiable Computation, Zero-knowledge proofs, FHE, homomorphic inference

<!-- page 2 -->

Table of Contents

Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1 Background on Rings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Polynomial Interactive Oracle Proofs for Rings . . . . . . . . . . . . . . . . 2.3 Proof-friendly CKKS and its arithmetization . . . . . . . . . . . . . . . . . . PIOPs for Unpacked Polynomials . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1 Packing and Unpacking polynomials in R q . . . . . . . . . . . . . . . . . . . . 3.2 PIOP for the Evaluation of Unpacked Polynomials on R q points . Our PIOP for Range Checks over Packed Polynomials . . . . . . . . . . . . . . Improved Arithmetization and PIOP Π AC for CKKS . . . . . . . . . . . . . . . 5.1 Layer consistency equations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Progressing through the layers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3 Prover algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Our PIOP for Evaluation of Sparse Polynomials . . . . . . . . . . . . . . . . . . . 6.1 Overview of the SparsePack PIOP . . . . . . . . . . . . . . . . . . . . . . . . . . . BatchFold . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.1 Batching Openings via CRT and HyperPlonk . . . . . . . . . . . . . . . . . 7.2 Batching BaseFold openings at a common point . . . . . . . . . . . . . . . Implementation and Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.1 BatchFold . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.2 High-level applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Additional Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A.1 Polynomial Commitments with Batched Evaluations . . . . . . . . . . . A.2 Compiling PIOPs into SNARKs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A.3 Round-by-Round Soundness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A.4 The Sumcheck Protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A.5 CKKS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A.6 A modular construction of the PIOP Π CKKS . . . . . . . . . . . . . . . . . Auxiliary Material on PIOP for Unpacked Polynomials . . . . . . . . . . . . . B.1 Proof of Theorem 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Auxiliary Material on PIOP for Range Checks . . . . . . . . . . . . . . . . . . . . . C.1 Proof of Lemma 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . C.2 Proof of Theorem 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Our Instantiation of the PIOP Π̂ range . . . . . . . . . . . . . . . . . . . . . . . . . . . . D.1 Correctness of Π̂ range . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . D.2 Security of Π̂ range . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . D.3 Efficiency of Π̂ range . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . D.4 A PIOP for Range Checks over a Finite Field . . . . . . . . . . . . . . . . . D.5 Our Optimized PIOP Π̂ range ............................... Additional material for Section 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . E.1 The copycon wiring predicate in Equation (7) . . . . . . . . . . . . . . . .

A

B

C

D

E

<!-- page 3 -->

E.2 Wiring predicates from [CCC + 25] . . . . . . . . . . . . . . . . . . . . . . . . . . . E.3 Too many gates in Equation (7)? . . . . . . . . . . . . . . . . . . . . . . . . . . . . E.4 Additional material for Section 5.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . E.5 Prover algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . F Putting everything together: The Π CKKS PIOP . . . . . . . . . . . . . . . . . . . F.1 Rearranging into the final oracles and final queries . . . . . . . . . . . . . G Auxiliary Material on SparsePack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . G.1 Our SparsePack PIOP for Evaluating Sparse Polynomials . . . . . . . G.2 Instantiations of SparsePack and Efficiency . . . . . . . . . . . . . . . . . . . G.3 Details on our instantiation of Π iptree . . . . . . . . . . . . . . . . . . . . . . . . H Details about BaseFold . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . H.1 The BaseFold Error Correcting Codes . . . . . . . . . . . . . . . . . . . . . . . . H.2 The BaseFold Commitment and Evaluation . . . . . . . . . . . . . . . . . . . H.3 Improvements on the minimum distance estimates of the BaseFold codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . I Implementation and Evaluation additional details . . . . . . . . . . . . . . . . . . I.1 Neural Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . I.2 Additional experimental results . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

<!-- page 4 -->

Introduction

Homomorphic encryption (HE) [Gen09] allows to compute directly over encrypted data, a crucial feature for data privacy in numerous applications. A notable use case is secure outsourcing of computation, allowing clients to delegate computations to untrusted servers, without revealing their inputs. For instance, in the context of Machine Learning as a Service (MLaaS), users can send encrypted queries to a server holding a model and receive encrypted results (e.g., predictions or classifications) in return. However, HE alone does not guarantee the integrity of the computation. While data remains private, clients have no assurance that the encrypted results returned by the server are correct. This creates a dangerous gap in HE-based solutions that leaves users vulnerable to maliciously manipulated outputs. In fact, in certain deployment scenarios, it has been shown that malicious use of the malleability feature of HE can lead to key-recovery attacks [LM21,GNSJ24,CCP + 24]. Tools to enforce the integrity of the computation can be crucial in providing solutions that counter such attacks [ABMP24]. Consequently, a line of research (see below for details on related works) addresses this problem by adding integrity properties to HE using another fundamental primitive: succinct non-interactive arguments of knowledge (SNARKs). SNARKs allow to prove the correctness of a computation in a way that can be efficiently checked. Thus one can use a SNARK to prove a homomorphic computation over HE ciphertexts, yielding what is called verifiable HE (vHE). Despite the tremendous progress in SNARKs research that brought them to a practical level that currently enables numerous applications, their use for vHE is not efficient in practice. This is because HE and SNARKs typically work over algebraic structures that are incompatible with each other. SNARKs work over large finite fields and are very efficient in proving arithmetic statements in this context, whereas HE works over polynomial rings with composite moduli, e.g., R q = Z q [Y ]/(Y N + 1), where q is a product of primes, and critically uses highly non-arithmetic operations for noise management. On top of that, due to the large size of HE ciphertexts (a single R q element can be 100-600KB), the actual homomorphic computation to be proven is much larger than its description over plaintexts. This situation makes general-purpose SNARKs non-ideal candidates for vHE due to overheads originating from emulation of ring arithmetic, nonalgebraic noise-management operations, and the size of ciphertexts. A recent work by Cascudo et al. [CCC + 25] took an important step toward reconciling the aforementioned arithmetic incompatibilities by introducing a new framework for building SNARKs for verifiable HE, focusing on the CKKS scheme [CKKS17]. Their approach begins with a proof-friendly version of CKKS whose performance is only slightly degraded compared to the original scheme, and whose homomorphic computations can be described with just two relations over R q : arithmetic circuit satisfiability and range checks. They then design a SNARK for these relations, by combining polynomial interactive oracle proofs (PIOPs) for them and a suitable polynomial commitment (PC). A key feature of their framework is that their PIOPs work over the ring R q , not the usual prime fields,

<!-- page 5 -->

and natively supports the HE arithmetic without emulation overheads. This approach shows promise, and [CCC + 25] provides initial evidence of efficiency gains over general-purpose SNARKs. Their evaluation fully confirms the practicality of the proof-friendly CKKS HE, but targets only two of the proving building blocks (sumcheck over R q and a variant of the Brakedown [GLS + 23] polynomial commitment) and indicates application-level efficiency estimates only for a small example consisting of one CKKS multiplication followed by noise flooding.

In this work, we continue this line of research on building verifiable computation (VC) for CKKS with the aim of achieving solutions that can, for the first time, scale to realistic HE applications. Our starting point is the recent work of Cascudo et al. [CCC + 25]. Despite the fact that their work represents significant progress over the state-of-the-art, several limitations remain that prevent their approach from scaling in practice. Most of them stem from the fact that [CCC + 25] designed their framework to be efficient with respect to circuit size, but did not fully address the fact that, by themselves, HE parameters can be very large and affect concrete performance, even if we view them as constants (for a fixed security level). In more detail:

- For a circuit with O(n) HE operations on an RLWE scheme √ over the ring R q = Z q [Y ]/(Y N +1), their polynomial commitment has O( nN log(q))-sized proofs and verification time. Although asymptotically efficient (sublinear in n), the N log(q) term already is in the order of hundreds of kilobytes – even for very small CKKS parameters. As the circuit grows, this cost quickly becomes impractical, effectively limiting [CCC + 25] to tiny HE circuits. - In dealing with noise maintenance operations, their protocol for range checks yields an O(N ) overhead to be paid by the polynomial commitment. Crucially, this overhead comes on top of the cost for committing to vectors of ciphertexts that inherently have their own O(N ) size. Considering that N is typically around 2 13 or larger, this overhead is significant. For instance, to prove that a vector of, say, n = 2 10 elements satisfies the range check, they need to additionally commit to at least four vectors of length 2 23 . - Their protocol for arithmetic circuits is based on a custom version of GKR [GKR08], and the main contribution of [CCC + 25] is to efficiently integrate the noise-management operations within the protocol. As typical in GKR, verifying for a circuit C either requires the verifier to do O(|C|) work to evaluate some polynomials that describe the circuit, or store commitments to these polynomials, and delegate their evaluation to the prover. [CCC + 25] does not address the concrete efficiency of this component. While this could be solved in theory with standard techniques, these – when adapted for a large ring like R q – would be prohibitively expensive. For instance, an approach similar to Spartan [Set20] would imply proofs in the order of GBs (see Section 8).

Our contributions. To achieve practically efficient verifiable HE for non-trivial circuits, we extend the framework of Cascudo et al. [CCC + 25] with new techniques that overcome its main limitations. Our approach yields substantial effi-

<!-- page 6 -->

ciency improvements on generic neural networks, demonstrating the feasibility of verifiable HE for MLaaS applications. √ BatchFold. To reduce the O( n) proof size of Brakedown commitments used in [CCC + 25], we build on BaseFold [ZCF24], which achieves O log 2 n proofs and O(n log n) proving time. Our main contribution (see Section 7) is a novel batching technique. For M independently committed polynomials f i with n coefficients over a finite field, we can prove multiple evaluations (y i = f i (x i )), reducing proof size and proving time from O(M log 2 n), using naive repetition, to O(M log n + log 2 n). Our batching technique has a twofold impact. The first obvious one is that we can batch evaluation proofs when compiling the PIOP into a SNARK. The second advantage is improving the complexity of our R q version of BaseFold even for evaluating a single polynomial. In a nutshell, a PC for R q is built by exploiting the CRT splitting of R q into a product of fields. Crucially, we use the fact that, for each prime factor p of q, there are N/4 isomorphic fields of characteristic p in the splitting, and thus we can apply batching over the N/4 polynomials in the CRT decomposition of the input polynomial. For a q, product of L + 1 different primes, we have a proof size of O(N L log n + L log 2 n) field elements (from fields of similar sizes) instead of O(N L log 2 n).

Packing and Unpacking in PIOPs. The PIOP for range checks of [CCC + 25] proves that each evaluation ṽ(b) in the boolean hypercube of a multilinear polynomial ṽ ∈ R q [X] is an element of R q = Z q [Y ]/(Y N + 1) with coefficients < B. To do this, [CCC + 25] introduces a decomposition technique that, ∀b ∈ {0, 1} ℓ , embeds the N coefficients of ṽ(b) into the evaluations h̃(b, k) of a freshly generated h̃ ∈ R q [X, Z] of ℓ + log N variables. This approach incurs an O(N ) overhead, especially for committing to h̃, an object N times bigger than ṽ. 4 In our paper, we introduce packing, a novel algebraic technique that allows PIOPs to prove statements about “unpacked” versions of multilinear polynomials. Analogously to the above decomposition, the unpacking of a polynomial p̃ ∈ R q [X] is a polynomial ũ ∈ R q [X, Z] with log N more variables and whose evaluations are all in Z q . The crucial difference though is that: (i) we do not commit to ũ, we only store and commit to p̃ in its dense (aka packed) form, (ii) the PIOP can work with an efficient sparse representation of ũ that has no O(N ) artificial overhead, and (iii) queries to ũ can be efficiently computed from queries to p̃. For this reason, we call ũ a virtual unpacked oracle. We refer to Section 3 for details on the technique. We discuss here two main applications. The first one is a new PIOP for range checks that avoids the O(N ) overhead of [CCC + 25], achieving not only an asymptotic improvement but also concrete orders of magnitude faster computing time. Specifically for the largest circuit of our experimental benchmark, we estimate [CCC + 25]’s range checks to take 1h20m in 48 threads, while ours takes less than 6 minutes single-threaded. Beyond range checks, we use packing to compress sparse polynomials over R q , such as the multilinear extensions of Z q -vectors in GKR. In particular, we

This decomposition and its overhead is reminiscent of the binary decomposition that creates additional (witness) bits and embeds them in a finite field.

<!-- page 7 -->

use packing to construct SparsePack, a new protocol for the evaluation of sparse polynomials, i.e., having sublinear nonzero evaluations in the hypercube. When applied to our case (MLEs of wiring predicates), it outperforms state-of-the-art solutions [Set20] featuring proofs that, in one of our benchmarks, are 41× shorter and 10× faster to prove (see Section 8).

Better arithmetization and preprocessing. One bottleneck of [CCC + 25] is handling the polynomials that describe the GKR circuit. These are as large as the circuit and hence cannot be computed by the verifier. Delegating this work to the prover is costly since, for a circuit of size 2 ℓ , these polynomials are of size 2 3ℓ , despite having only O 2 ℓ nonzero evaluations. To address this, we introduce a new arithmetization for CKKS circuits that improves upon [CCC + 25] in several ways. We design closed-form polynomials for the wiring predicates related to CKKS homomorphic multiplication which the verifier can compute efficiently. We also substantially reduce the number and size of the polynomials that encode the structure of the target FHE circuit (which is arbitrary). Finally, we use SparsePack to prove the evaluations of these sparse polynomial (see above).

Experiments. The framework of [CCC + 25] enabled, for the first time and with minimal emulation overhead, verifiability for complete HE multiplications with non-linear noise management operations. However, the authors only presented estimates for a single ciphertext multiplication. Our improvements can scale beyond that: we provide experiments for small Neural Networks of multiplicative depth 2, containing between 48 and 192 total ciphertext multiplications each. We measure performance for our new packed range proofs and batched polynomial commitment scheme, and estimate it for our sparse commitments, showing that these NNs can be proven in the order of minutes single-threaded. This represents a major improvement over [CCC + 25], which estimated 25 seconds for a single multiplication in 48 threads. Additionally, we present execution time and proof size for commitments over R q using Batchfold, showing a factor of 2.8 (resp. 9.5) improvement in execution time (resp. proof size) compared to Basefold.

Related work. Literature on verifiable computation for FHE can be divided in two main approaches. The first one, formalized in [FGP14], consists in designing VC schemes for proving computations on FHE ciphertexts. With the exception of recent work of Cascudo et al. [CCC + 25], prior works in this line suffer from either supporting only variants of HE schemes with limited applicability [FGP14,FNP20,BCFK21], or otherwise incurring large overheads for emulating ring or noise-maintenance operations [GNS23,KVH24,VKH23]. The second approach computes proofs homomorphically over the plaintext space [GGW24,ACGS23,GBK + 24]. While this approach can be faster than proving ciphertext computations, it has inherent limitations, notably: it cannot achieve public verifiability, since proof verification requires decryption 5 ; it cannot sup-

Public verifiability, by definition, cannot rely on secret material. Nevertheless, any designated verifier scheme can be turned into a “semi-publicly verifiable” one by making the verifier provide a publicly verifiable ZK proof of their execution of the verification algorithm. This idea is instantiated with proofs of decryption in [GBK + 24].

<!-- page 8 -->

port approximate schemes such as CKKS (due to their lack of a ring structure on the plaintext space) and it is vulnerable to verification oracle attacks.

Preliminaries

For a positive integer n, [n] denotes the set {0, . . . , n − 1}. We denote vectors v in bold, start indexing at 0 and denote its i-th coefficient by v[i] or v i . We denote by v [B] the truncation of v to its first B terms, v [A,B) for its terms in the range [A, B) (i.e. v [A,B) = (v A , . . . , v B−1 )) and v [A,B] for its terms in the range [A, B]. We define |v| the length of v and #(v) = ⌈log 2 (|v|)⌉. Let to-int : {0, 1} ∗ → Z be n the function that, on input P a binary vector j ∈ {0, 1} , for any positive integer n, returns the integer k∈[n] j k · 2 k . Let bin : Z → {0, 1} ∗ be its inverse. Given a finite set S, we write a ← $ S to mean that a is sampled uniformly at random from S and e ← χ to mean that e is sampled according to some distribution χ. We often invoke the infinity norm ∥·∥ ∞ . Given a vector v of elements in R q := Z q [Y ]/(Y N + 1), we apply the norm coefficient-wise: the expression ∥v∥ ∞ < B means that all the monomial coefficients of v are within the range [0, B − 1]. An indexed relation R is a set of tuples ( i , x ; w ) where i is the index, x the statement and w the witness. The language L(R) associated to a relation R is the set of pairs ( i , x ) for which there exists a witness w such that ( i , x ; w ) ∈ R.

2.1

Background on Rings

We restrict ourselves to finite commutative rings with unity, which we often denote by R. Given a ∈ R, [a] b denotes the reduction of a modulo b. If a ∈ R(Y ) is an element of a polynomial ring, a[j] (resp. a[j]) denotes its j-th (resp. to-int(j)-th) coefficient (in such representation) and [a] b denotes the coefficientwise modular reduction. For a vector v ∈ R n , [v] p denotes modular reduction of each component of v.

Definition 1. An exceptional set is a subset Ŝ ⊂ R with the property that a − b is an invertible element of R for each pair of distinct elements a, b ∈ Ŝ.

We denote by R[X 1 , . . . , X ℓ ] the polynomials in ℓ variables and coefficients in R and by R (≤d) [X 1 , . . . , X ℓ ] the subset of polynomials of individual degree ≤ d.

Lemma 1 (Generalized Schwartz-Zippel). Let f ∈ R[X 1 , . . . , X ℓ ] be a nonzero polynomial of total degree d. Let Ŝ ⊂ R be an exceptional set. Then, d . Pr (r 1 ,...,r ℓ )← Ŝ ℓ [f (r 1 , . . . , r ℓ ) = 0] ≤ | Ŝ|

The multilinear extension (MLE) of a function f : {0, 1} ℓ → R is the (unique) multilinear polynomial f ˜ : R ℓ → R such that f ˜ (b) = f (b) for all b ∈ {0, 1} ℓ . For any ℓ ≥ 1, let eq : {0, 1} ℓ × {0, 1} ℓ → {0, 1} be the equality predicate ˜ be its MLE, which has closed-form (i.e., eq(a, b) = 1 iff a = b) and let eq Q ℓ ˜ representation eq(X, Y ) = j=1 (X j Y j + (1 − X j )(1 − Y j )) computable in time O(ℓ) [Tha13]. The MLE of any function f : {0, 1} ℓ → R is defined by the

<!-- page 9 -->

polynomial f ˜ (X 1 , . . . , X ℓ ) =

P

˜ X 1 , . . . , X ℓ ). Analogously, the b∈{0,1} ℓ f (b) · eq(b,

2 ℓ

MLE of a vector v ∈ R (which for convenience we index in binary) is the P ˜ polynomial ṽ(X 1 , . . . , X ℓ ) = b∈{0,1} ℓ v[b] · eq(b, X 1 , . . . , X ℓ ).

2.2

Polynomial Interactive Oracle Proofs for Rings

We recall polynomial interactive oracle proofs (PIOP) for rings [CCC + 25] using the notion of (indexed) oracle relations of [CBBZ23].

Definition 2 (Oracle Relations). An indexed oracle relation R is an indexed relation in which the index i and the statement x include pointers to oracle polynomials with coefficients in a ring R, and the polynomials are part of the witness w . A pointer to a polynomial p is denoted by JpK.

Definition 3 (Polynomial IOPs). Let R be a ring and R be an indexed oracle relation for (multivariate) polynomials with coefficients in R. A polynomial IOP for R is an interactive protocol between a prover P and a verifier V, compactly denoted by ⟨P( i , x , w ), V( i , x )⟩. In each round the prover P( i , x , w ) sends oracle polynomials and/ or ring elements, and the verifier V( i , x ) sends random challenges. Each oracle JpK specifies the number of variables ℓ and the degree in each variable. The verifier can query all the oracles, the ones sent by the prover and the ones included in ( i , x ), at arbitrary points r ∈ R ℓ . At the end of the execution, V accepts or rejects. See Appendix A for the efficiency metrics. Correctness: For any honest execution of ⟨P( i , x , w ), V( i , x )⟩ on ( i , x ; w ) ∈ R, the verifier accepts. δ-Soundness: A PIOP is δ-sound if for any unbounded adversary Adv and any ( i , x ) ∈ / L(R), Pr [⟨Adv( i , x ), V( i , x )⟩ = 1] ≤ δ

δ-Knowledge Soundness: A PIOP is δ-knowledge-sound if there exists a PPT oracle machine Ext (which can query all the oracle polynomials at arbitrary points) such that for any adversary Adv and any ( i , x ) h i Pr b = 1 ∧ ( i , x ; w ) ∈ / R : ⟨Adv( i , x ), V( i , x )⟩ = b, w ← Ext Adv ( i , x ) ≤ δ.

PIOPs can also satisfy the notion of round-by-round (RBR) soundness [CCH + 19], which allows a tighter quantification of the loss incurred when applying the Fiat- Shamir transformation, and a better analysis of protocols with parallel repetition (see Appendix A.3 for more details).

Lemma 2 ([CBBZ23, Lemma 2.3]). Consider a δ-sound PIOP for oracle relations R such that for all ( i , x , w ) ∈ R, w consists only of polynomials such that the statement contains oracles to these polynomials. The PIOP has δ-knowledgesoundness, and the extractor runs in time O(| w |).

We generalize the notion of virtual oracles from [CBBZ23].

<!-- page 10 -->

Definition 4 (Virtual oracles). Given a function g and oracles {Jp 1 K, . . . , Jp k K}, a virtual oracle Jp ∗ K = Jg(p 1 , . . . , p k )K consists of the list of oracles and functions ev g , h 1 , . . . , h k such that, for any x, ev g (p 1 (h 1 (x)), . . . , p k (h k (x)), x) = p ∗ (x).

In other words, the functions associated to the virtual oracle allow one to compute a query to the virtual oracle Jp ∗ K at x by querying each oracle Jp j K on some x j = h j (x) and then computing p ∗ (x) from their results.

Sumcheck protocol. Let R be a ring, p : R ℓ → R be an ℓ-variate polynomial of degree at most d in each variable. The sumcheck (oracle) P relation R sum is the set of tuples (y; p) (resp. ((y, JpK); p)) such that y = b∈{0,1} ℓ p(b). The sumcheck protocol [LFKN90] is an interactive proof (resp. a PIOP) for R sum where the verifier needs to only compute (resp. query) p at a point (r 1 , . . . , r ℓ ). While originally defined for finite fields, it also generalizes to rings R if the random challenges are sampled from an exceptional set Ŝ ⊂ R. We denote the sumcheck PIOP by Π sum ; for completeness we present it in Appendix A.4. Also, we denote by Π sum a variant of the PIOP Π sum changed so that the verifier samples random challenges in an exceptional set Ŝ 0 ⊂ Z q .

Polynomial commitments and compilation to SNARKs. Prior work shows how to compile PIOPs into SNARKs via polynomial commitments (PC), a cryptographic primitive that allows committing to a polynomial p and later proving that y = p(a) with a succinct proof. In our work, we use an extension of this paradigm that relies on PCs with batched evaluation proofs. In a nutshell, this is a generalization of PCs that allow generating a single proof about the evaluations of multiple, say M , polynomials at multiple points, i.e., ∀i ∈ [M ] : y i = p i (a i ), and has the advantage that the resulting proof size is smaller than concatenating M proofs. For space reasons, see Appendix A.1 for more formal details.

2.3

Proof-friendly CKKS and its arithmetization

In this work we use the proof-friendly version of the CKKS homomorphic encryption scheme [CKKS17] introduced in [CCC + 25]. For a full description of the scheme, see Appendix A.5 or [CCC + 25]. Here we only discuss the main technical points that are useful to build our proof system.

Choice of the ring and exceptional sets. Fast CKKS implementations Q use the L ciphertext ring R q = Z q [Y ]/(Y N +1), where N is a power of two and q = i=0 p i for primes p i . In proof-friendly CKKS, p i = 2aN/d + 1 for an odd integer a and a power of two d. Thus, Y N + 1 factors over Z p i into k = N/d irreducible (2j+1) polynomials Y d − ζ i , where ζ i is a primitive 2N/d-th root of unity. By the Q Q (2j+1) ∼ k−1 L ∼ CRT, R q = i=0 j=0 R i,j , with each R i,j = Z p i [Y ]/(Y d − ζ i ) = F p di . This structure yields exceptional sets large enough for soundness, bounded by the smallest field component. We use two sets, Ŝ 0 ⊂ Z q and Ŝ N ⊂ R q , of sizes p min and p dmin respectively (where p min is the smallest p i ). For example, −128 setting d = 4 (resp. d = 2) for 32-bit (resp. 64-bit) primes makes p −d , min ≈ 2 i.e., negligible for security parameter λ = 128; using Ŝ 0 may instead require

<!-- page 11 -->

repetitions to amplify soundness. Concretely, we take Ŝ N diagonal: each of its elements has the same exceptional element of F p di in all the k components R i,j of each p i (Appendix G.2 discusses it further).

Since R q decomposes into copies of F p di , we cannot use full NTTs to accelerate HE operations and instead use incomplete NTTs. We note that efficient implementations of incomplete NTTs have been widely explored in the literature, and can even lead to performance improvements in some cases [HYS + 25,AHKS22,LS19]. In [CCC + 25], the authors incur a slowdown of just 20% compared to “regular CKKS” due to the use of incomplete NTTs. Since we make use of their scheme unmodified, our construction also inherits their slowdown. We note this modification in the ciphertext ring has no bearing upon the underlying plaintext ring or slots. We adopt the standard plaintext encoding C N/2 → C[X]/(X N + 1) [CKKS17], but one could also use others [JPK + 24,Kim25].

Remaining in the same ring R q . Standard levelled CKKS uses a moduli chain q := q L > · · · > q 0 (where q i = q i+1 /p i+1 ). In contrast, proof-friendly CKKS operates entirely over a single ring R q L = R q . Operations normally altering the ring (e.g., modulus switching) have their results re-embedded back into R q L via the map ι l : R q l ,→ R q L , x 7→ x̃ · z l , where x̃ ∈ R q L is a lift of x and P l z l := i=0 Q i Q̂ i = CRT( 1, . . . , 1 , 0, . . . , 0) ∈ R q L with Q i = q L /p i and Q̂ i = | {z } l+1 times (q L /p i ) −1 p i defining the CRT map. As discussed in [GNS23,CCC + 25], this abstraction effectively emulates modular reductions and quotient ring arithmetic without impacting performance.

Arithmetization of proof-friendly CKKS. At the core of [CCC + 25] is a procedure that translates a computation C ′ (x) = y, where C ′ is a circuit of (proof-friendly) CKKS additions and multiplications (see sec.A.5), into a relation over R q . Ciphertext additions are trivially described by additions over R q . Other operations such as key switching and rounding (required for ciphertext multiplication) cannot be expressed by arithmetic operations over R q without significant overhead. For KeySwitch, the prover inputs w ks,0 , . . . , w ks,l ∈ R q , satisfying ∥w ks,i ∥ ∞ < p i and such that they recompose to the original value in R q via the CRT map (which is an arithmetic operation over R q ).

Regarding Rescale, suppose we have an element x ∈ R q l , in its RNS representation x = ([x] p 0 , [x] p 1 , . . . , [x] p l , [0] p l +1 , . . . , [0] p L ). The division and rounding of x by the current level l can be proved via Euclidean division by p l . The prover’s inputs are w rmd = ([w rmd ] p 0 , . . . , [w rmd ] p L ) and w quot = ([w quot ] p 0 , . . . , [w quot ] p L ). The range proof shows that ∥w rmd ∥ ∞ < p l and that ∥w quot ∥ ∞ < q l /p l . Finally, recalling that z l = CRT( 1, . . . , 1 , 0, . . . , 0) ∈ R q L , we check that x · z l = | {z }

l+1 times

(w quot · p l + w rmd ) · z l . This shows that proof-friendly CKKS multiplications can be expressed as a sequence of arithmetic operations over R q and a finite number of range checks relations for R q elements.

<!-- page 12 -->

One can apply this argument to a generic circuit C ′ organized into D multiplica- (j) (j) (j) (j) tive layers of width W . 6 Denoting by w ks,0 , . . . , w ks,j , w rmd , w quot the vectors of non-deterministic inputs for level j, the whole computation can be described in terms of two oracle relations:

R range = {( i , x ; w ) := (B, J w̃K; w̃) : ∥ w̃∥ ∞ < B}

## R AC = {( i , x ; w ) := (C, (Jx̃K, JỹK, J w̃K); (x̃, ỹ, w̃)) : C(x, y, w) = 0} ,

where C is an arithmetic circuit over R q of constant-depth, obtained by flattening the CKKS circuit C ′ . For the details, see [CCC + 25]. Importantly, since all of the RNS primes have the same bit length, one can batch all the range proofs (i) (i) for {w ks,j , w rmd } i,j together by approximating the bounds to 2 u , their nearest power of two. Let Jx̃K, JỹK, J w̃ 2 u K, J w̃ l K be the oracles of the MLEs of the inputs (D−1) x, outputs y := w quot , prover’s values for RNS decompositions and remainders

(D−1)

w 2 u := w ks,0 ∥ . . . ∥w ks,D−1 ∥ . . . ∥w ks,0

(D−1)

∥w rmd ∥ . . . ∥w rmd

and prover’s values

(l) for quotients w l := w quot , for l = 0, . . . , D − 2. The relation that describes the

computation C on CKKS ciphertexts can be compactly written as:

n D−2 R CKKS = (C, (Jx̃K, J w̃ 2 u K, {J w̃ l K} D−2 l=0 , JỹK); (x, w 2 u , {w l } l=0 , y)) :      D−2  ^ q L−D+1 q L−l D−2 u C(x, y, w 2 u , {w l } l=0 ) = 0 ∧ ∥w 2 u ∥ ∞ < 2 ∧ ∧ ∥y∥ ∞ < ∥w l ∥ ∞ < | {z } p L−l p L−D+1   l=0 R AC  {z }  | 

R range

A modular PIOP Π CKKS for R CKKS can be built from PIOPs Π range for R range and Π AC for R AC using a simple ‘and’ composition (see Appendix A.6). Also, notice that we include the circuit C as part of the index i ; this allows the verifier to preprocess C once and later verify proofs in time poly(log |C|).

PIOPs for Unpacked Polynomials

In this section we give a set of useful results that allow us to construct PIOPs that can prove statements about “unpacked” versions of multilinear polynomials in R q [X], which can be seen as a way to define statements about their Z q coefficients. Our techniques generalize to any ring R and polynomial ring R̂ := R[Y ]/I(Y ), where I(Y ) ∈ R[Y ] of degree N . For ease of exposition, we limit the presentation to our rings of interest R = Z q and R̂ = R q = Z q [Y ]/(Y N + 1).

Packing and Unpacking polynomials in R q

3.1

Let R q = Z q [Y ]/(Y N + 1) for N = 2 ν . We consider multivariate polynomial rings R q [X 1 , . . . , X ℓ ] and R q [X 1 , . . . , X ℓ , Z 1 , . . . , Z ν ]. For brevity, we denote X = (X 1 , . . . , X ℓ ) and Z = (Z 1 , . . . , Z ν ). We define two useful functions,

Layers are numbered from 0 to D − 1, with inputs at level 0 and outputs at level D−1. Without loss of generality, one can assume that all layers have the same width.

<!-- page 13 -->

pack and unpack, that allow switching between two different representations of a multilinear polynomial in R q [X]. The function unpack takes a multilinear polynomial p̃ ∈ R q [X] and returns a multilinear polynomial ũ ∈ R q [X, Z], of degree 0 in Y , which can be naturally identified with Z q [X, Z], and is defined as follows:

unpack : R q (≤1) [X] → R q (≤1) [X, Z]

7→ ũ(X, Z) =

p̃(X)

˜ p̃(b)[k] · eq((b, k), (X, Z)).

b∈{0,1} ℓ k∈{0,1} ν

unpack essentially extracts all the coefficients in the variable Y of the evaluations of p̃ in the hypercube, and encodes these coefficients under the basis ˜ { eq(k, Z)} k∈{0,1} ν instead of {Y k } k∈[N ] . While unpack intuitively goes from (a subset of) Z q [X, Y ] to Z q [X, Z], we stress that its outputs are embedded in R q [X, Z]. We informally call polynomials in the image of unpack unpacked polynomials. The function pack : R q [X, Z] → R q [X] instead is defined as follows: u(X, Z) 7→ p(X) = u(X, k) · Y to - int(k) .

k∈{0,1} ν

Notice that in general pack is not the inverse of unpack, yet for any multilinear p̃ one can see that p̃ = pack(unpack(p̃)). In particular, given a multilinear polynomial ũ(X, Z) that has degree 0 in Y , pack “packs” ũ into a dense polynomial with fewer variables, hence the name.

Evaluating unpacked polynomials. A key property of unpacked polynomials (formalized in the Lemma below) is that an evaluation of an unpacked polynomial on Z q -elements can be computed from the evaluation of its packed version. 7

Lemma 3. Let uEval be the function that on inputs a ∈ R q and z ∈ Z νq returns ˜ uEval(a, z) = a[k] · eq(k, z).

k∈{0,1} ν

(≤1)

Then for any polynomial p̃ ∈ R q [X], ũ = unpack(p̃), and any (x, z) ∈ Z ℓq ×Z νq : uEval(p̃(x), z) = ũ(x, z), and uEval is computable with O(N ) operations in Z q .

(≤1)

˜ ˜ x) ∈ Proof. Observe that the polynomials eq(b, X) ∈ R q [X] are such that eq(b, Z q if x ∈ Z ℓq . This allows to define the coefficients a[k] of p(x) as follows ˜ ˜ p̃(x) = p̃(b) eq(b, x) = p̃(b)[k]Y to - int(k) eq(b, x)

b∈{0,1} ℓ



b∈{0,1} ℓ k∈{0,1} ν



N −1

˜ p̃(b)[k] eq(b, x)  Y to - int(k) =

=



k∈{0,1} ν

b∈{0,1} ℓ

{z

|

=a[k]∈Z q

a[k]Y k .

k=0

}

Precisely, we mean evaluations on elements of R q of degree 0 in Y ; for simplicity we abuse notation and denote this subset of R q by Z q .

<!-- page 14 -->

PIOP Π ueval for ((y 1 , x 1 , . . . , y a , x a , Jp̃K); p̃) ∈ R ueval

Let ℓ ′ = ℓ + ν, X = (X 1 , . . . , X ℓ ′ ), Z = (Z 1 , . . . , Z ν ). 1. V sends σ ← $ Ŝ 0 ν , τ P ← $ Ŝ P 0 . ˜ ˜ x i )[k] · eq(Z, k) · T i−1 ∈ Z q [X, Z, T ] 2. Let E(X, Z, T ) = ai=1 k∈{0,1} ν eq(X, P P ˜ and Ẽ σ,τ (X) = E(X, σ, τ ). Let ỹ(Z, T ) = k∈{0,1} ν eq(k, Z) ai=1 y i [k]·T i−1 .

P and V run Π sum for ((ỹ(σ, τ ), Jf K); f ) ∈ R sum where f = unpack(p̃) · Ẽ σ,τ . Given Π sum .V’s query to Jf K on r = (r 1 , r 2 ) ∈ Z ℓ+ν , the verifier Π ueval .V: q P P ˜ x i )τ i−1 , parsed as ψ = k ψ[k]Y to - int(k) , - computes ψ = P ai=1 eq(r, ˜ - computes ψ ∗ = k ψ[k] eq(k, σ), - makes a query to Jp̃K on r 1 and receives answer v = p̃(r 1 ), - returns uEval(v, r 2 ) · ψ ∗ to Π sum .V.

Figure 1: PIOP for R ueval

By plugging the above definition of a[k] into the definition of uEval ˜ ˜ ˜ a[k] · eq(k, z) = p̃(b)[k] · eq(b, x) · eq(k, z),

k∈{0,1} ν

b∈{0,1} ℓ k∈{0,1} ν

which is = ũ(x, z) by construction of unpack in Eq. (1). The computability of uEval in time O(N ) follows by an algorithm from [VSBW13] that computes all the multilinear Lagrange polynomials in time O(2 ν ). ⊔ ⊓

Unpacked Virtual Oracles. A useful implication of Lemma 3 is that we can create virtual oracles (see Definition 4) of unpacked polynomials and run a PIOP on a virtual oracle Jg(ũ 1 , . . . , ũ k )K, where each ũ i = unpack(p̃ i ) and g is a function that admits virtual oracles. This holds as long as the PIOP’s verifier queries to each unpacked oracle Jũ i K are only on points of Z q . This implication follows simply by seeing that for unpack, the associated functions ev unpack , h for the virtual oracle (see Definition 4), are ev unpack = uEval and h(x, z) = x. In Appendix A.4, we give a simple example of how to use a virtual unpacked polynomial to P prove a sumcheck y = b∈{0,1} ℓ ,k∈{0,1} ν p̃(b)[k] over the Z q coefficients.

PIOP for the Evaluation of Unpacked Polynomials on R q points

3.2

The result of Lemma 3 shows how to compute the evaluation of an unpacked polynomial on Z q -points, given evaluations of its packed version. In this section, we address the more general problem of evaluating an unpacked polynomial on points of R q . While these evaluations cannot be directly reduced to evaluations of the packed polynomial, here we present a protocol that allows proving such evaluation. Precisely, we present a PIOP Π ueval for the following oracle relation:

R ueval = {((y 1 , x 1 , . . . , y a , x a , Jp̃K); p̃) : ∀i y i = ũ(x i ) where ũ = unpack(p̃)}.

The full description of Π ueval is in Figure 1. Here we present the ideas in more detail and justify its correctness. For simplicity, we focus on the case of evaluating

<!-- page 15 -->

at a single point, i.e., a = 1; the extension to more points is straightforward observing that the aggregation random challenge τ ∈ Ŝ 0 ⊂ Z q . The goal is to prove that for ũ = unpack(p̃) it holds y = ũ(x), which can be written as follows (where ℓ ′ = ℓ + ν). ˜ ˜ ũ(x) = ũ(b) eq(b, x) = ũ(b) eq(b, x)[k] Y to - int(k) {z } | ν ℓ ′ ℓ ′

b∈{0,1}

b∈{0,1}

k∈{0,1}

Ẽ(b,k)

ũ(b) Ẽ(b, k)Y to - int(k) =

=

ℓ ′

k∈{0,1} ν

b∈{0,1}

y[k]Y to - int(k) .

k∈{0,1} ν

In particular, the last equality follows from the fact that ũ(b) as well as Ẽ(b, k) are in Z q . Therefore, we can reduce testing y = ũ(x) to checking that for all P k ∈ {0, 1} ν , y[k] = b ũ(b) Ẽ(b, k). These are 2 ν sumchecks that we can batch together by sampling a random σ and checking ˜ ỹ(σ) = y[k] eq(k, σ) = ũ(b) Ẽ(b, σ).

k∈{0,1} ν

b∈{0,1} ℓ ′

This is done by running the PIOP Π sum (i.e., the sumcheck PIOP with the verifier’s random challenges in Ŝ 0 ⊂ Z q ), which ends with the verifier querying ũ(r) and Ẽ(r, σ). The query to ũ can be computed through P a query to p̃ using ˜ uEval. Ẽ(r, σ) can be computed by the verifier as ψ = σ), where k ψ[k] eq(k, P ˜ ψ = eq(x, r), parsed as ψ = k ψ[k]Y to - int(k) . To see correctness: X X ˜ ˜ ˜ ˜ ˜ Ẽ(r, σ) = Ẽ(b, k) eq(b, r) eq(k, σ) = eq(b, x)[k] eq(b, r) eq(k, σ)

b,k

˜ ˜ eq(x, r)[k] · eq(k, σ) = ψ ,

=

k

P

˜ where last equality follows from eq(x, r) =

b

k

˜ ˜ ˜ x) eq(b, r) and eq(b, r) ∈ Z q . b eq(b,

Theorem 1. Π ueval is a PIOP for R ueval with perfect completeness, prover’s efficiency O a2 ℓ+ν , verifier’s efficiency O(ℓ + a · N ), 3(ℓ + ν) log q bits of communication, and δ ueval -knowledge soundness with δ ueval = (a − 1 + 2ℓ + 3ν)/| Ŝ 0 |.

Remark 1 (Parallel repetition of Π ueval ). If the exceptional set Ŝ 0 is not large enough to make 1/| Ŝ 0 | negligible, we apply κ-fold parallel repetition, denoted (κ) κ/(ℓ+ν) κ Π ueval , that achieves soundness δ ueval and RBR-soundness δ ueval (see The- (κ) orem 4) [CCH + 19]. The efficiency of Π ueval is κ times that of Π ueval and its verification requires κ queries to the (packed) oracle Jp̃K.

Our PIOP for Range Checks over Packed Polynomials

In this section, we present our new PIOP for range checks that improves over the prior solution from [CCC + 25]. More precisely, we construct a PIOP for

R range = {( i , x ; w ) = (T B , JṽK; ṽ) : ∀b ∈ {0, 1} ℓ ṽ(b) ∈ T B },

<!-- page 16 -->

(≤1)

where R q := Z q [Y ]/(Y N + 1), ṽ ∈ R q [X 1 , . . . , X ℓ ], and T B is the table of size B N containing all the elements of R q with coefficients in [0, B − 1]. As shown in [CCC + 25], extending ideas of [STW24] from finite fields to R q , one can reduce a lookup in T B into c · N lookups in the smaller table t β = (0, . . . , β − 1) for β = B 1/c . This uses a lemma similar to Lemma 4 below with a slight difference caused by our use of unpack. See Appendix C for the proof.

Lemma 4. Let B = 2 b , N = 2 ν , let c = 2 γ such that c | b and β = B 1/c . Let T B be the table defined above, and t β = (0, . . . , β − 1). Then for any ṽ ∈ (≤1) R q [X 1 , . . . X ℓ ], (T B , JṽK; ṽ) ∈ R range if and only if there exists (≤1) µ̃ ∈ Z q [X 1 , . . . , X ℓ , Z 1 , . . . , Z ν , Z 1 ′ , . . . , Z γ ′ ] such that, for ũ = unpack(ṽ),

∀i ∈ {0, 1} ℓ+ν : ũ(i) =

∀b ∈ {0, 1} ℓ+ν+γ : µ̃(b) ∈ t β

µ̃(i, j) · β to - int(j)

j∈{0,1} γ

Based on this Lemma, one can construct a PIOP Π range for proving that (T B , JṽK; ṽ) is in R range by letting the prover send a polynomial µ̃ and then showing that (i) µ̃ satisfies equation (5), i.e., its evaluations are in the smaller table t β , and (ii) µ̃ is correctly related to ṽ according to equation (4), i.e, it is a β-decomposition of unpack(ṽ). The protocol of [CCC + 25] followed a similar approach by constructing a PIOP for each of these equations; 8 however, a large (≤1) source of inefficiency in their case stems from embedding µ̃ in R q [X, Z, Z ′ ] which, in spite of its sparsity, is an object that is c · N times bigger than ṽ. In particular, this causes an O(N ) overhead in the entire protocol. In this paper, we avoid this overhead through the combination of two techniques. First, we embed µ̃ over a different ring H q = Z q [Y ]/h(Y ) and prove that it satisfies equation (5) for the table t β ⊂ Z q via a PIOP over H q . Crucially, we choose H q to be much smaller than R q , as d = deg(h) ≪ N is a small constant (e.g., d = 2 or 4) that ensures the existence of a large enough exceptional set Ŝ d ⊂ H q (we explain how we choose h below). With this choice, the PIOP running over H q avoids altogether an O(N ) overhead. In Appendix D we also give an optimized variant that takes H q = F p for a large prime p, which we use in Section 8. To complete the picture, we need to connect the range proof about µ̃ to the polynomial ṽ, which is the end-goal of Π range . To this end, we relate µ̃ ∈ (≤1) (≤1) H q [X, Z, Z ′ ] with ṽ ∈ R q [X] according to equation (4), and leverage our unpacked evaluation technique to let the verifier query ũ = unpack(ṽ) without requiring the prover to commit to ũ. We remark that our technique is similar to the ring-switching used in [HMZ25], although in that work it is primarily used to transform an R1CS statement over R q into one over a Galois ring where the entire computation is eventually done, while in our case the change of ring is used (in combination with our unpacking

Precisely, equation (4) is encoded differently without the unpack encoding.

<!-- page 17 -->

technique) for the specific task of proving ranges. Moreover, the ring-switching technique of [HMZ25] was later used in [NOZ26] to construct lattice-based multilinear polynomial commitments with concrete efficiency in verification. In what follows we present our protocol in more detail. Q L Q k−1 Our PIOP Π range . Consider the splitting of R q ∼ R described = i=0 i,j j=0

(2j+1)

in section 2.3, where each R i,j = Z p i [Y ]/(Y d − ζ i ) is isomorphic to the field Q L F p di . We set H q = Z q [Y ]/h(Y ) as a ring isomorphic to i=0 R i,0 by the CRT, i.e., where for all i, h(Y ) mod p i = (Y d − ζ i ). This choice ensures the existence of an exceptional set Ŝ d ⊂ H q of size p dmin , where p min = min{p 0 , . . . , p L }. Let R̂ range be an oracle relation over (t β , Jµ̃K; µ̃) defined in the same way as R range except that its index is restricted to tables t β ⊂ Z q and the relation is defined over multilinear polynomials µ̃ with coefficients in H q . It is easy to see (≤1) that we can rephrase Lemma 4 by embedding µ̃ in H q [X, Z, Z ′ ] and replacing the condition of equation (5) with (t β , Jµ̃K; µ̃) ∈ R̂ range . We construct a PIOP Π range for R range with table T B by using a PIOP Π̂ range for R̂ range with the smaller t β , 9 combined with a probabilistic test to check equation (4). The full description of Π range is in Fig. 2. The protocol proceeds as follows. The prover computes the unpacking of ṽ and its β-decomposition according to equation 4 and sends the oracle Jµ̃K to the verifier. Then the goal is to convince the verifier that (t β , Jµ̃K; µ̃) ∈ R̂ range and that ṽ and µ̃ satisfy equation (4). The former is achieved by executing the PIOP Π̂ range (step 3 in Fig. 2). For the latter, the idea is to test that the polynomial P ũ(X, Z) is a linear combination of partial evaluations of µ̃, i.e., ũ(X, Z) = j µ̃(X, Z, j)β to - int(j) . Intuitively, this could be tested by evaluating the polynomials P on a random point, i.e., querying ũ(r) and µ̃(r, j) for all j and testing ũ(r) = j µ̃(r, j)β to - int(j) . However, these polynomials are over different rings with different exceptional sets. To solve this issue we take the random point r in the exceptional set Ŝ 0 ⊂ Z q , that is common to both R q and H q . −λ However, since Ŝ 0 is not large enough to make 1/| Ŝ 0 | = p −1 we repeat min ≈ 2 this test κ times. Notably, since this parallel repetition test happens in a single −λ round we can take the smallest κ that make p −κ ; e.g., for our choice min ≈ 2 of 45-bit primes (see Appendix I) we take κ = 3. The last problem to solve is that the test above requires querying a polynomial ũ that is larger than ṽ by a factor of N . We define ũ as an unpacked virtual oracle, and using the fact that the random challenges are in Ŝ 0 ⊂ Z q , we apply our result of Lemma 3, which reduces queries to ũ = unpack(ṽ) to queries to the (dense) packed polynomial ṽ. The proof of the following theorem appears in Appendix C.2.

Theorem 2. Let Ŝ d ⊂ H q , and Ŝ 0 ⊂ Z q be exceptional sets. Let Π̂ range be a PIOP for R̂ range with perfect completeness and RBR-knowledge error δ̂ range . Then Π range is a PIOP with perfect completeness and RBR-knowledge error δ range = max(( ℓ+ν ) κ , | κ·γ , δ̂ ). | Ŝ | Ŝ | range

d

We assume B a power of 2; see [CCC + 25] for the extension to the general case.

<!-- page 18 -->

PIOP Π range for (T B , JṽK; ṽ) ∈ R range

(≤1)

(≤1)

1. P computes ũ = unpack(ṽ) ∈ R q [X, Z] and µ̃ ∈ H q [X, Z, Z ′ ] as the decomposition of ũ according to equation (4), and sends Jµ̃K. V samples r 1 , . . . , r κ ← $ Ŝ 0 ℓ+ν and sends them to P. 2. P sends µ̃ ∗ i (Z 1 ′ , . . . , Z γ ′ ) = µ̃(r i , Z 1 ′ , . . . , Z γ ′ ), for i = 1 to κ. V samples s ← $ Ŝ d γ and, for i = 1 to κ, queries the oracle Jµ̃K on (r i , s), and the virtual oracle JũK = P Junpack(ṽ)K on r i . Then V checks the following: ∀i = 1, . . . , κ: ũ(r i ) = j∈{0,1} γ µ̃ ∗ i (j) · β to - int(j) and µ̃(r i , s) = µ̃ ∗ i (s)

3. P and V run a PIOP Π̂ range for (t β , Jµ̃K; µ̃) ∈ R̂ range .

Figure 2: Construction of the PIOP Π range from Π̂ range

To obtain the final protocol Π range , we need to instantiate the PIOP Π̂ range for the relation R̂ range where the table in the index is [0, β − 1] ⊂ Z q and the PIOP works over the ring H q . We set this protocol to be the same as that in [CCC + 25] with the only difference that instead of working over R q and its exceptional set Ŝ N ⊂ R q , we redefine it over the ring H q with exceptional set Ŝ d . For completeness, we give a full description of Π̂ range in Appendix D, and present an optimized version in Appendix D.5. We also defer to Appendix D.5 a discussion on its efficiency, and we give a full efficiency analysis for concrete parameters in Section 8.

Improved Arithmetization and PIOP Π AC for CKKS

We construct a PIOP for the relation R AC (Section 2.3) which, combined with Π range from the previous section, yields a PIOP for proving computations on CKKS ciphertexts, following [CCC + 25]. We refer to Appendix F for an explanation about which of the polynomial oracles from this section are in common with the input oracle Π range , i.e., which values require a range check. We improve upon the arithmetization of CKKS in [CCC + 25] on several fronts. First, we replace their arithmetic circuit for R AC with a more expressive one which allows to “copy” (into a MLE Ṽ 3,copy ) the results of plaintext-ciphertext products without going through base decomposition and rescaling. We also allow plaintext inputs from the prover, provided through an oracle MLE Ṽ 3,ptxt . This enables commit-and-prove SNARKs where the prover commits to Ṽ 3,ptxt . Second and most importantly, by careful labeling of the wires in this new circuit, we construct MLEs for the wiring predicates that are sparse in a very structured way, and have significantly fewer variables. Beyond the obvious improvement of reducing the amount of variables, this structured sparsity speeds up the sumcheck-based layer consistency equations in different ways:

- We provide specialized linear-time prover algorithms that improve upon a generic application of the algorithms from [XZZ + 19,ZLW + 21];

<!-- page 19 -->

- For wiring predicates that are independent of the structure of the HE circuit (i.e. the ones that describe base decomposition and rescaling), we provide closed form equations that the verifier can easily evaluate on their own; - For those that are not, we provide efficient polynomial commitments in Section 6 that exploit the structured sparsity. There are up to 7 oracles of this form in our work, depending on the actual circuit structure. For example, if we only wanted to capture the less expressive relation R AC in [CCC + 25] without plaintext inputs, we would only have 3 oracles of this form. - For a HE circuit of depth D, the PIOP of [CCC + 25] had 13 + 2(D − 1) sparse polynomials in the index and D + 1 dense polynomials in the witness. We describe how to implement our more expressive relation with up to 7 sparse polynomials (with fewer variables) and a single dense one for the witness.

Notation: Within this section, let δ = ⌈log 2 (D)⌉ and let µ = ⌈log 2 (2M )⌉ + δ, where D is the depth of the HE circuit and M is the number of HE multiplications in its layer with the most multiplications. We denote vector of variables as X = (X 0 , X 1 , . . .) and refer to the leftmost one as the least significant one. By abuse of notation, we use d 2 (resp. d 0 , d 1 ) to refer to the set of wires holding the d 2 (resp. d 0 , d 1 ) output of premultiply, according to the notation in Appendix A.5. For a boolean vector x, V i,S (x) denotes the value on wire x for the set of wires S in GKR layer i (not to be confused with the CKKS level). Due to space constraints, the predicates already introduced in [CCC + 25] are given in Appendix E. Table 1 gives information about the amount of variables in the different MLEs for the intermediate values of the circuit, as well as what they are meant to index from their least to their most significant variables. Some subset of these variables can be thought of as “metadata”. For example, each predicate has δ variables which, together, index one of the D layers in the HE circuit. Table 1 does not include Ṽ 3,copy , Ṽ 3,ptxt and Ṽ in , since we do not need closed form equations for the predicates that interface with them. Notice that the overhead of adding our different forms of metadata is small. For example, without the “HE level metadata”, predicates in Table 1 would need to have as many variables as log 2 of the number of their relevant wires in the whole HE circuit. Given the metadata, we only need to have as many variables as the maximum among such relevant kind of wires on each level. For example, let {d 2,j } D−1 j=0 represent the subset of d 2 wires that belong to the j-th HE layer. The MLE Ṽ 2,d 2 (X [#(d 2 )] ) is such that #(d 2 ) = δ + max({#(d 2,j )} D−1 j=0 ) = µ − 1. Let us now explain how we achieve the closed form equations for the MLEs and in particular their structured sparsity and reduced amount of variables. Whereas the first technique originates from [ZLW + 21], to the best of our knowledge we are the first ones to exploit the other two we present.

[ZLW + 21] trick: In our layer consistency equations, rather than having a different set of variables for every kind of wiring predicate (as in [CCC + 25]), we use the same set of variables X for all of them as much as possible. This results in equa- P P ] j (Z, x) · Ṽ i j (x [l j ] ) where l j is the tions of the form Ṽ out (Z) = j x∈{0,1} l gate

] j (Z, x) amount of variables in Ṽ i j and l = max j (l j ). While it could seem that gate

<!-- page 20 -->

LSPs Middle positions MSPs Bits Meaning Bits Meaning Bits Meaning Z Gate number (for that type) - - Ṽ 0 T 0 , T 1 Gate type Ṽ 1 Z [δ] HE level Z δ key-switch output type: c ′ 0 vs c ′ 1 Z (δ,µ) wire on level Ṽ 2,d 01 Z [δ] HE level Z δ pre-mult output type: d 0 vs d 1 Z (δ,µ) wire on level Ṽ 2,d 2 Z [δ] HE level Z [δ,µ−1) wire carrying pre-mult output d 2 - - Ṽ 2 Z 0 d 01 vs d 2 As Ṽ 2,d 01 or Ṽ 2,d 2 Ṽ 3,BD X [δ] HE level Z [δ,µ−1) wire carrying pre-mult output d 2 X [δ,2δ) specific p i Y δ mult output type: c ′′ 0 vs c ′′ 1 Y (δ,µ) wire on level Ṽ 3,quot Y [δ] HE level Ṽ 3,rc 3 X [δ] HE level Z [δ,µ) Z δ : c ′′ 0 vs c ′′ 1 | Z (δ,µ) : wire on level X δ rmd vs quot

Table 1: Variable information for the different intermediate-values MLEs. LSPs = Least significant positions, MSPs = Most significant positions.

is not truncated accordingly, we internally modify that MLE so as to selectively ] j (Z, x) = e ] j (Z, x [l j ] ). reduce the boolean hypercube, i.e. gate f q(1, x [l j ,l) ) · gate

Metadata: Our pieces of “metadata” in the wires allow to easily apply the levelappropriate constants when describing the MLEs for the wiring predicates that correspond to the rescaling and base decomposition operations.

X to Z: Finally, a precise labelling of the wires involved in the expression

Ṽ out (Z) =

j

x∈{0,1} l

] j (Z, x) · Ṽ i j (x [l j ] ) gate

] j (Z, x) which internally have terms e results in MLEs gate f q(Z [l j ′ ] , X [l j ′ ] ) of significant length. Whenever such a factor is present, one may hope to drop the corresponding l j ′ summation variables altogether and feed Z [l j ′ ] directly into Ṽ i j , obtaining expressions that look as follows, where l ′ = max j (l j − l j ′ ):

Ṽ out (Z) =

x∈{0,1} l ′

j

] j (Z, x) · Ṽ i j (Z [l j ′ ] , x [l j −l j ′ ] ). gate

This reduces the amount of X variables, which are the ones driving the efficiency of the sumcheck protocol. The substitution, however, is not always legitimate: It may only be applied to those variables which the wiring predicate constrains exclusively through the equality factor e f q(Z [l j ′ ] , X [l j ′ ] ). If the predicate uses them for anything else, the right hand side of Eq. (6) increases its degree in those variables and stops being the multilinear polynomial Ṽ out . It still agrees with Ṽ out on the boolean hypercube, but not at the random point at which the GKR verifier evaluates the layer consistency equation, so an honest prover would be rejected. As we will see in Section 5.1, the substitution is therefore not applied to the “HE level” metadata variables of the predicates that select level-dependent ^ 3 , e g constants ( rescon ^ 3 , bdcon vk), which are kept in X.

<!-- page 21 -->

5.1

Layer consistency equations

For a reminder of the wiring predicates in [CCC + 25] see Appendix E.2. In the following, we adapt those through the application of the three techniques outlined above. We directly provide the MLEs of these new variations.

Layer 0: Let us start by looking at the MLE for the output layer Ṽ 0 . We define an extra vector of variables T = (T 0 , T 1 ) as metadata for output wires. For T = (0, 0) it is the output of a rescon gate, for T = (1, 0) output of a bdcon gate and for T = (0, 1) it is a copycon gate. The reason to add such variables rather than simply relying on Z to identify a gate is that it is simpler to write the MLEs of each different gate using the eq predicate, all while being able to group all of them into a single sumcheck for what should be Ṽ 0 (T, Z) = 0. Given the presence of T, we can limit the length of the vector Z: It only has as many variables as the maximum among the three kinds of gates: Z = (Z 0 , . . . , Z max(µ,µ−1,#(copy))−1 ). Let d = #(V 3,ptxt ), let m = max(2δ, d) and let m ′ = 1 + max(µ, #(in)). We apply the X → Z optimization to all variables except the δ ones indexing the HE level of the layer-3 input wire, which we read from X [δ] . Eq. (7) provides a sumcheck-style consistency check for the output layer Ṽ 0 . Later on, Equations (8), (9), (10) and (30) describe the MLEs of its wiring predicates.

^ 2 (T) · Ṽ 2,d 2 (Z [µ−1] ) + rescon 0 = Ṽ 0 (T, Z) = bdcon ^ 1 (T) · Ṽ 1 (Z [µ] )

− copycon ^ 3,copy (T) · Ṽ 3,copy (Z [#(copy)] ) ^ 3 (T, Z [δ] , x) · Ṽ 3,BD (x [δ] , Z [δ,µ−1) , x [δ,2δ) ) + bdcon

x∈{0,1} m

+ rescon ^ 3 (T, Z [δ] , x) · Ṽ 3,rc 3 (x [δ] , Z [δ,µ) , x δ ) + copycon(T, ^ Z [#(copy)] , x, y) · f (x [d] , y) ,

y∈{0,1} m ′

where f (X [d] , Y) = Ṽ 3,ptxt (X [d] ) · g(Y) and g(Y) = (1 − Y m ′ −1 ) · Ṽ in (Y [#(in)] ) + Y m ′ −1 · Ṽ 3,quot (Y [µ] ). One important further improvement that we do just for this layer consistency equation is that we also truncate Z on the right hand side of Eq. (7). This improves efficiency without introducing any new attacks (see Appendix E.3). Notice how the X → Z optimization is applied to the wire-indexing variables of Ṽ 3,BD and Ṽ 3,rc 3 (namely Z [δ,µ−1) and Z [δ,µ) ), which the corresponding predicates constrain only through an equality factor, but not to their HE-level variables, which are read from X [δ] . The three predicates that carry no X at all, ^ 2 , rescon bdcon ^ 1 and copycon ^ 3,copy , are trivially compatible with the substitution and their terms are therefore left outside the sum. Every summand of Eq. (7) is then multilinear in Z, so the equation is an identity of polynomials and can be evaluated at the random point at which Π AC invokes it. Next, we explain the MLEs of each individual wiring predicate.

^ 1 (T) is trivial. The description of rescon ^ 3 is a bit Rescaling consistency rescon complicated, since it takes multiple values. Notice that half of the inputs in layer

<!-- page 22 -->

3 are quotients (which we will select when X δ = 1, and simply multiply by the suitable p l ) and the other half are remainders (selected when X δ = 0). Since the first δ variables in X hold the HE level of the input wire, we use them to select whether a particular input wire to the z-th rescon gate (which holds a quotient value, i.e. with X δ = 1) has to be multiplied by −p l , or −p 2 etc. Further multiplying e f q(bin(l), X [δ] ) with e f q(bin(l), Z [δ] ) forces the level of the input wire to agree with the level of the rescon gate.

rescon ^ 1 (T) = e f q(T, (0, 0))

rescon ^ 3 (T, Z [δ] , X) = −f eq(T, 0) · e f q(X [δ+1,m) , 1)· D−1 e f q(bin(l), Z [δ] ) · e f q(bin(l), X [δ] ) · 1 − X δ + X δ p l .

l=0

^ 3 similarly to rescon ^ 3 . Base decomposition consistency We define bdcon

^ 2 (T) = e bdcon f q(T, (1, 0))

^ 3 (T, Z [δ] , X) = −f bdcon eq(T, (1, 0)) · e f q(X [2δ,m) , 1)· D−1 e f q(bin(l), Z [δ] ) · e f q(bin(l), X [δ] )·

l=0

l

i=0

e f q(bin(i), X [δ,2δ) ) · PW ω l (1)[i] .

Copying values consistency The copycon(t, ^ z, x, y) MLE selects values of x, y P such that, for a given z it holds that x,y ptxt[x] · ctxt[y] = ctxt [z], where ctxt [z] is the copied result. All plaintexts are stored in Ṽ 3,ptxt (x [d] ) (for which the verifier has oracle access). The variable Y m ′ −1 chooses whether ctxt comes from Ṽ in (y [#(in)] ) (known to the verifier) or Ṽ 3,quot (y [µ] ) (prover’s oracle). Ṽ 3,copy (Z [#(copy)] ) stores ctxt ′ [z]. Since there is one ctxt ′ [z] copy per check and copycon(t, z, ·, ·) is satisfied by as many pairs (x, y) as the fan-in of that copy gate, the term carrying Ṽ 3,copy has to sit outside the sum over x, y, for which we use

copycon ^ 3,copy (T) = e f q(T, (0, 1)).

Note that the choice between Ṽ in and Ṽ 3,quot is made inside the sum, by Y m ′ −1 . See Appendix E for the precise definition of the copycon predicate.

Layer 1: In this layer, let Z = (Z 0 , . . . , Z µ−1 ). Ṽ 1 (Z) contains the outputs of key switching. Eq. (11) checks consistency between Ṽ 1 (Z) and the d 0 , d 1 outputs of pre-multiply (stored in Ṽ 2,d 01 (Z), in layer 2) mixed with the inner product of the evaluation key and the base decomposition of d 2 . Ṽ 1 (Z) = Ṽ 2,d 01 (Z) + e g vk(Z [δ+1] , x) · Ṽ 3,BD (x [δ] , Z (δ,µ) , x [δ,2δ) ) . (11)

x∈{0,1} 2δ

<!-- page 23 -->

Here too the HE-level variables of Ṽ 3,BD are kept in X, since e g vk uses the level to pick the evaluation key digits evk l,b [i] and hence it is not of the form required by the X → Z optimization. The MLE can be thus written as:

D−1

e f q(Z δ , b) ·

e g vk(Z, X) =

b=0

l=0

l

e f q(bin(l), Z [δ] ) · e f q(bin(l), X [δ] )·

e f q(bin(i), X [δ,2δ) ) evk l,b [i] .

i=0

Layer 2: Finally, consistency between the values Ṽ 2 (Z) on layer 2 and those in layer 3 can be done through the predicate for inner products Xmult(z, x, y) from [LXZ21]. Let s ′ = max(#(in), µ, #(copy)). In Eq. (12), we limit the length of the vectors x, y to s ′ by having different, specific versions of Xmult for each kind of product that can occur. Xmult i,i is an Xmult between in wires, Xmult q,q between quot wires, Xmult q,c between quot and copy wires, and so on. In layer 2, Ṽ 2 (Z) is such that Z = (Z 0 , . . . , Z µ ) and ^ i,i (Z, x, y) · Ṽ in (x [#(in)] ) · Ṽ in (y [#(in)] )+ Ṽ 2 (Z) = Xmult

x,y∈{0,1} s ′

^ q,q (Z, x, y) · Ṽ 3,quot (x [µ] ) · Ṽ 3,quot (y [µ] )+ Xmult

^ i,q (Z, x, y) · Ṽ in (x [#(in)] ) · Ṽ 3,quot (y [µ] )+ Xmult

^ i,c (Z, x, y) · Ṽ in (x [#(in)] ) · Ṽ 3,copy (y [#(copy)] )+ Xmult

^ q,c (Z, x, y) · Ṽ 3,quot (x [µ] ) · Ṽ 3,copy (y [#(copy)] )+ Xmult

^ c,c (Z, x, y) · Ṽ 3,copy (x [#(copy)] ) · Ṽ 3,copy (y [#(copy)] ) . Xmult

Depending on the HE circuit that is captured by this equation, some of the terms of the sum can be removed if they are known to be zero.

5.2

Progressing through the layers

The Π AC PIOP starts by invoking the sumcheck protocol on Eq. (7) and moving towards GKR-layer 3. We describe such series of reductions. For a set of wires S j , Ṽ S j (r j ) denotes its MLE evaluations for the random sumcheck challenges r j . After the execution of sumcheck for Eq. (7), and in order to reduce to a claim about Ṽ 1 (r 1 ) together with a claim about Ṽ 2,d 2 (r 2 ), the verifier needs to check the final claim from the prover by querying oracles J Ṽ 3,BD K, J Ṽ 3,rc 3 K, J Ṽ 3,quot K, ^ 2 , J Ṽ 3,ptxt K, J Ṽ 3,copy K, J copyconK ^ and evaluating the closed form equations of bdcon ^ bdcon 3 , rescon ^ 1 , rescon ^ 3 , copycon ^ 3,copy , Ṽ in at the relevant challenge points. The value Ṽ 1 (r 1 ) is plugged into Eq. (11). Completing a sumcheck reduction to Ṽ 2,d 01 (r 01 ) requires V to query J Ṽ 3,BD K and evaluate e g vk at the new challenges.

<!-- page 24 -->

Claims Ṽ 2,d 01 (r d 01 ) and Ṽ 2,d 2 (r d 2 ) need to be combined into a claim Ṽ 2 (r 2 ). In order to do this, we follow the approach from [CCC + 25], which employs sumcheck too. Due to space constraints, we give those details in Appendix E.4. The reduction requires V to evaluate MLEs e C 2,d 01 , e C 2,d 2 at the relevant challenges. Finally, Ṽ 2 (r 2 ) is substituted in Eq. (12), where for a general circuit V has to evaluate Ṽ in on their own (twice) and query oracles JXmult i,i K, JXmult q,q K, JXmult i,q K, JXmult i,c K, JXmult q,c K, JXmult c,c K once and oracles J Ṽ 3,quot K, J Ṽ 3,copy K twice. If all checks pass, this concludes Π AC . Notice how the whole protocol requires up to 17 oracle queries for a generic circuit. In Section 8, since we can simplify Eq. (12), we require a lot less.

5.3

Prover algorithms

Our description in Section 5.2 is focused on the verifier. In Appendix E.5, we provide linear time prover algorithms that follow the techniques in [XZZ + 19,ZLW + 21]. We improve upon them by exploiting our structured sparsity in different forms. One general philosophy is that we always start to challenge from the least significant variables up to the most significant ones. This has positive impacts due to the fact that the prefixes which enable sparsity are placed in the most significant position. We provide more efficient algorithms to update the function evaluation tables according to this challenge ordering rule, specialize for our specific wiring predicates and equations, show how to compute the sumcheck for the product of sparse vectors of different length, etc.

Our PIOP for Evaluation of Sparse Polynomials

In this section, we present a PIOP, dubbed SparsePack, for proving the evaluation of a collection of sparse polynomials with coefficients in Z q . More formally, let us define the indexed relation R speval over tuples ( i , x , w ) such that: the index i = (Jp 0 K, . . . , Jp a−1 K) consists of a multilinear polynomials in m variables such that each p i evaluates to a non-zero Z q -value in at most 2 ℓ locations of {0, 1} m ; the statement x = (x 0 , y 0 , . . . , x a−1 , y a−1 ) consists of a evaluation points in R q m , and alleged results y i ∈ R q ; the witness w consists of the polynomials p 0 , . . . , p a−1 . Then the relation is R speval := {( i , x , w ) : ∀i ∈ [a] p i (x i ) = y i }. The SparsePack PIOP is a crucial building block of the PIOP for R AC . It enables the prover to convince the verifier about the correct evaluation of the ^ i,i , Xmult ^ q,q , Xmult ^ i,q , Xmult ^ i,c , Xmult ^ q,c , Xmult ^ c,c 7 polynomials copycon, ^ Xmult that encode the description of the circuit (see Section 5). For a circuit of size |C| such polynomials have m ≈ 3 log |C| variables and ≈ 2 ℓ = O(|C|) nonzero evaluations, all of them in Z q and most of them being simply 1 as they encode wiring predicates. Naively using a standard polynomial commitment (PC) on these polynomials would incur Ω(2 3ℓ ) proving time, i.e., cubic in the circuit size. An alternative solution is to use a PC for sparse polynomials whose state of the art is represented by Spark [Set20] (as generalized in [STW24]). Despite being designed to work over finite fields, Spark might be extended to work in R q but

<!-- page 25 -->

unfortunately the large size of R q , compared to the usual size of finite fields used in standard SNARKs, reduces its concrete efficiency. We estimated the efficiency of Spark for parameters N = 2 13 , log q ≈ 135, ℓ = 15, m = 34, a = 2 that fit one of our neural network applications (cf. Appendix G) and compared it with the PIOP SparsePack that we present in this section. In a nutshell, the Spark-based solution would have a proof size of about 6.5 GiB while SparsePack yields a 163 MiB proof. The main reason of this gain is that Spark requires the prover to generate at least a⌈m/ℓ⌉ = 6 commitments to R q -polynomials of size 2 ℓ and later prove evaluations of 24 polynomials (6.2 GiB with two batched Basefold proofs over R q as in [CCC + 25]). In contrast, our PIOP does not require generating any commitment at proving time and it only requires the prover to compute a single evaluation proof for a polynomial commitment computed during preprocessing. Notably, by using our packing techniques, this committed preprocessed polynomial can be of size 2 ℓ+log m+log a+2−log N = 2 11 , much smaller than in Spark. The size of this evaluation proof is 163 MiB with BatchFold. Note that, in terms of computation time, we also eliminate the need to commit to polynomials at proving time, which in Spark would take about 10 minutes of work. Finally, we also obtain another gain in the size of the information-theoretic part of the proof, which with Spark would be 235 MiB, while in SparsePack it can be as low as 25 KiB. We provide more details of this comparison in Section 8 and Appendix G.

Overview of the SparsePack PIOP

6.1

In this section we explain the main ideas of our SparsePack PIOP, and refer to Appendix G for its full description, security proof and efficiency analysis.

Sparse encoding Let S = {s 0 , . . . , s 2 ℓ −1 } ⊂ {0, 1} m be a subset of cardinality 2 ℓ such that {k ∈ {0, 1} m : p(k) ̸ = 0} ⊆ S. From now on we assume that m = 2 µ is a power of 2 (otherwise we can generalize the arguments below by appropriate ℓ µ padding of zeros). Let S ∈ {0, 1} 2 ×2 be the matrix with rows indexed by elements in {0, 1} ℓ and whose b-th row contains s to - int(b) ∈ S ⊂ {0, 1} m . Then a sparse p can be represented with two multilinear polynomials val p and ind p where ind p is the MLE of the above matrix S and val p is such that

∀b ∈ {0, 1} ℓ : val p (b) = p(ind p (b, 0), . . . , ind p (b, 1)).

For a polynomials p 0 , . . . , p a−1 , each assumed to have up to 2 ℓ nonzero evaluations, we can define (larger) polynomials val, ind containing all their sparse encodings such that, denoting α = ⌈log a⌉ and setting p i := 0 for a ≤ i < 2 α ,

∀(b, i) ∈ {0, 1} ℓ+α : val(b, i) = p i (ind(b, i, 0), . . . , ind(b, i, 1)).

(≤1)

Ideas of the proof. To prove (∀i ∈ [a], p i (x i ) = y i ), let ỹ ∈ R q [Z 1 , . . . , Z α ] (≤1) be the MLE of the vector (y 0 , . . . , y a−1 ) and let x̃ ∈ R q [Z 1 , . . . , Z α+µ ] be the

<!-- page 26 -->

MLE of the vector of inputs (x 0 , . . . , x a−1 ), i.e., such that x̃(i, j) = (x i ) j . Then we can express the statement to be proven as ˜ Z) = ˜ Z) eq(k, ˜ ỹ(Z) = p i (x i ) eq(i, p i (k) eq(i, x i )

i∈{0,1} α

˜ Z) val(b, i) eq(i,

=

(b,i)∈{0,1} ℓ+α

i∈{0,1} α ,k∈{0,1} m

Y

˜ eq(ind(b, i, j), x̃(i, j)).

j∈{0,1} µ

Using standard techniques, we can test this polynomial equation on a veriα fier’s random challenge t ← $ Ŝ N , reducing the problem to proving Y ˜ t) ˜ val(b, i) eq(i, eq(ind(b, i, j), x̃(i, j)). ỹ(t) =

(b,i)∈{0,1} ℓ+α

j∈{0,1} µ

The statement above is a highly structured computation which involves an inner product and 2 ℓ+α trees of multiplications of depth µ, performed in parallel. Therefore, we present SparsePack generically as a family of protocols parametrized by a PIOP for proving a statement like that of Equation (14). To instantiate this PIOP we considered two options—Thaler’s multiplication protocol [Tha13] and a parallel version of Quark’s grand product [SL20]. In SparseP- ack, we adopted the former as it avoids creating fresh commitments during the proof. A straightforward use would be expensive due to computing µ sequential sumchecks and due to the need, in the end, to perform an evaluation proof on the committed polynomials describing the sparse encoding, of size am2 ℓ . In SparsePack we leverage the power of our packing technique to reduce these costs. More formally, for an integer β, let Π iptree be a PIOP for the oracle relation Y R iptree = {(v, Jf 1 K, Jf 2 K, JEK) : v = f 1 (b, i)f 2 (i) E(b, i, j)},

(b,i)∈{0,1} ℓ+α

j∈{0,1} β

and in which the verifier makes one query to each oracle polynomial: f 1 (r 1 , r ′ 1 ), f 2 (r 2 ), E(r, s). It is easy to see how to use Π iptree to prove Equation (14) ˜ by running it on (ỹ(t), JvalK, J eq(X, t)K, JE µ K) where, for Z = (Z 1 , . . . , Z α+µ ), ˜ E µ (X, Z) = eq(ind(X, Z), x̃(Z)), which is multilinear in X and of degree 2 in Z. We improve on this solution through the following techniques.

Packing and Preprocessing. The polynomials val, ind have all coefficients in Z q . Thus, assuming that α+µ+2 ≤ ν = log N , which for our values of α = 3 and ν−5 log N ≈ 13 would be satisfied for circuits of size up to ≈ 2 2 /3 ≈ 2 85 , we can ℓ pack val, ind into a single polynomial pol of size 2 . However, since we have space to pack even more information in pol, we leverage that the p i polynomials are part of the index (thus they are not adversarially generated) to create additional polynomials in a deterministic preprocessing that allows us to reduce the depth of the multiplication tree in (14). We do this Q as follows: we observe that the product in Equation (14) can be also written as j∈{0,1} µ−1 E µ (b, i, j, 0)E µ (b, i, j, 1). Let Z = (Z 1 , . . . , Z α+µ−1 ).

<!-- page 27 -->

While running Π iptree with the polynomial Ê µ (X, Z) = E µ (X, Z, 0)·E µ (X, Z, 1) would make the tree of smaller depth, the degree of Ê µ would double in all variables and proving its evaluation would vanish the gain in depth. Instead, we use preprocessing to create polynomial that allows Q an additional us to replace the product of (14) by j∈{0,1} µ−1 E µ−1 (b, i, j), where E µ−1 has degree 1 in X and degree 2 in Z. To do this, let ind ∗ be the MLE of (ind(b, i, j, 0) · ind(b, i, j, 1) : ∀b, i, j), and let x̃ ∗ be the MLE of x̃(i, j, 0)x̃(i, j, 1). Let us define the following polynomials

x̃ ∗ 0 (Z) = −2 · x̃ ∗ (Z) + 2 · x̃(Z, 0) + x̃(Z, 1) − 1

x̃ ∗ 1 (Z) = −2 · x̃ ∗ (Z) + x̃(Z, 0) + 2 · x̃(Z, 1) − 1

x̃ ∗ 2 (Z) = 4 · x̃ ∗ (Z) − 2 · x̃(Z, 0) − 2 · x̃(Z, 1) + 1

x̃ ∗ 3 (Z) = x̃ ∗ (Z) − x̃(Z, 0) − x̃(Z, 1) + 1 E µ−1 (X, Z) = ind(X, Z, 0)x̃ ∗ 0 (Z) + ind(X, Z, 1)x̃ ∗ 1 (Z) +ind ∗ (X, Z)x̃ ∗ 2 (Z) + x̃ ∗ 3 (Z).

By construction, it holds ∀b, i, j: E µ−1 (b, i, j) = E µ (b, i, j, 0)E µ (b, i, j, 1). Therefore, in SparsePack we run Π iptree with the virtual oracle JE µ−1 K; this α+µ−1 ℓ . Interestends with a verifier’s query v = E µ−1 (r, s), with r ∈ Ŝ N , s ∈ Ŝ N ingly, answering this query requires no additional sumcheck: by Equation (15), E µ−1 is a linear combination of ind(X, Z, 0), ind(X, Z, 1) and ind ∗ (X, Z) whose coefficients x̃ ∗ i (Z) depend only on the public inputs. Hence the verifier computes the values x̃ ∗ i (s) on its own and obtains v from the three queries ind(r, s, 0), ind(r, s, 1), and ind ∗ (r, s). In SparsePack, we create a polynomial pol of ℓ + α + µ + 2 variables that puts together val, ind and ind ∗ , but then we pack pol into a polynomial pol with only n = (ℓ + α + µ + 2 − ν) variables. In particular, the three queries above become evaluations of pol on points that differ only in two coordinates, and we batch them into a single query to pol using two random challenges. We refer to Appendix G for the details.

Evaluating the (un)packed polynomial. The solution sketched above requires querying the unpacked JpolK on points in R q , so we cannot use Lemma 3 to compute them from queries to JpolK. The last piece of the protocol, which solves this issue, is again a tool of our packing technique, namely our PIOP Π ueval of Section 3.2 for proving evaluations of unpacked polynomials on R q points.

BatchFold

In this section, we describe our polynomial commitment (PC) scheme to elements in R q [X], which instantiate the PIOP oracles. For efficiency, our goal is to allow for batched openings of the form f m (z m ) = y m , for m ∈ [M ], at a smaller cost sublinear in M . We do this in two steps: we first reduce this question to constructing PC schemes over finite fields with batched openings of polynomials f m at a common point z. Then we instantiate the latter from BaseFold [ZCF24].

<!-- page 28 -->

7.1

Batching Openings via CRT and HyperPlonk Q L Q k−1 Recall that R q ∼ = i=0 j=0 R i,j , where each R i,j is a finite field of size p di Q L Q k−1 and d = N/k (in practice, d = 4). Let Φ : R q → i=0 j=0 R i,j denote the aforementioned isomorphism and Φ ij : R q → R i,j its components. We extend Φ and Φ ij to R q ℓ by applying them coordinate-wise, and to R q [X] coefficient-wise. In [CCC + 25], given polynomial commitments PC R i,j for each R i,j [X 1 , . . . , X ℓ ], the authors construct a unified PC R q for R q [X 1 , . . . , X ℓ ]. This boils down to committing to each CRT component, i.e., PC R q .Com(f ) := (PC R i,j .Com(Φ ij (f ))) i,j , and the evaluation function (for single openings) PC R q .Eval shows f (z) = y by running each PC R i,j .Eval on the claim Φ ij (f )(Φ ij (z)) = Φ ij (y). Our first (elementary) observation is that this can be extended to more general Eval M protocols for batches of M evaluations: to prove {f m (z m ) = y m : m ∈ [M ]}, apply each PC R i,j .Eval M on {Φ ij (f m )(Φ ij (z m )) = Φ ij (y m ) : m ∈ [M ]}.

Batching on isomorphic components. More interestingly, we can use the observation that for every i ∈ [L + 1], the fields {R i,j } k−1 j=0 are isomorphic to each k−1 other. Therefore, all {PC R i,j } j=0 can be captured by a single scheme PC i . Then, if each PC i is endowed with a PC i .Eval kM (batching kM openings) we can construct PC R q .Eval M (batching M openings) that only uses each PC i .Eval kM once. Indeed, to prove {f m (z m ) = y m : m ∈ [M ]}, apply PC i .Eval kM to prove the claim {Φ ij (f )(Φ ij (z m )) = Φ ij (y m ) : j ∈ [k], m ∈ [M ]}, for every i ∈ [L + 1]. This amounts to L + 1 batched evaluations proofs, rather than k(L + 1) (if we were to apply PC i .Eval M k times) and is beneficial given that one execution PC i .Eval kM is cheaper than k executions of PC i .Eval M , as we will see.

Reducing to evaluations on the same point. We now reduce the task of constructing Eval M to creating a protocol Eval com M that proves batched opening at a : proves claims of the form {f m (z ′ ) = y m common evaluation point, i.e. Eval com M m ∈ [M ]} for a common z ′ . In Figure 3, we construct PC.Eval M from PC.Eval com M by using an idea from HyperPlonk [CBBZ23]. The overhead of this protocol is an additional sumcheck over {0, 1} ℓ . The soundness error of Eval M is at most 2ℓ+M −1 + error Eval com where error Eval com is the soundness error of Eval com M , and F is |F| M M the field over which PC is defined (in our case, for each PC i , F is of size p di ).

7.2

Batching BaseFold openings at a common point

BaseFold. We summarize the relevant features of BaseFold. A detailed description can be found in Appendix H. The commitment to a polynomial f is given by an oracle π d (in practice, a vector commitment) to an encoding of its coefficient vector with certain linear error-correcting code C d , of dimension 2 ℓ (the number of coefficients of f ). P The protocol PC.Eval for a single opening f (z) = y ˜ consists of a sumcheck for b∈{0,1} ℓ f (b) eq(b, z) = y, and a consistency check for the fact that π d is indeed an oracle to an element in C d and is consistent with the sumcheck. The soundness of the evaluation protocol of PC depends on

<!-- page 29 -->

Construction of PC.Eval M from PC.Eval com M

1. The verifier sends s ← $ F to the prover. For every b ∈ {0, 1} ℓ the prover defines P M −1 m ˜ s · eq(b, z m ) · f m (b). Let h̃ be the multilinear extension the value h b := m=0 of the h b , i.e. the unique h̃ ∈ F ≤1 [X 1 , . . . , X ℓ ] with h̃(b) = h b ∀b ∈ {0, 1} ℓ . 2. Prover P and verifier now engage in a standard sumcheck protocol for the state- P M −1 m · y m where, when the verifier ment m=0 s b∈{0,1} ℓ h̃(b) = S for S :=

queries h̃(r) for some r ← $ F ℓ : (a) The prover opens {q m = f m (r), m ∈ [M ]} with P PC.Eval com M . −1 m ˜ · eq(r, z m ) · q m (b) If this is correct, the verifier computes h̃(r) = M m=0 s The verifier accepts if the sumcheck (and the PC.Eval com M opening) passes.

Figure 3: Construction of PC.Eval M from PC.Eval com M

PC.Eval com M : Batched opening proof at common point z P M −1 m 1. The verifier sends s ← $ F. The prover sets u(X) := m=0 s f m (X). This P M −1 m implicitly defines π d := π d,u = m=0 s π d,f m . P −1 m 2. The prover and verifier compute S = M m=0 s y m and engage in PC.Eval for the claim: “π d oracle to Enc d (u) such that u(z) = S”. When the verifier queries π u at a coordinate µ, this is answered with the answers a m to queries π d,f m at P of −1 m µ, for all m ∈ [M ]. The verifier can then compute the answer as M m=0 s a m .

Figure 4: Batched opening of M evaluations at common point.

the minimum distance of the code C d and can be found in Appendix H, where we show an slight improvement with respect to the results in [ZCF24].

Batching at the same point. Our construction for PC.Eval com M is given in Figure 4 where we leave the PC.Eval of Basefold implicit. In Appendix H, Figure 12 we out that we provide the full protocol PC.Eval com M including PC.Eval. Here we point P M −1 m to applying PC.Eval on a linear combination u = reduce PC.Eval com M m=0 s f m , where queries to u are obtained by querying all f m ’s; since other than making these queries and computing the linear combination of the results, the rest of PC.Eval com M is independent of M (it is essentially a single application of PC.Eval), we obtain an advantage over repeating PC.Eval M times. We have the following soundness (see Appendix H, Lemma 9).

−1 Lemma 5. The soundness error of PC.Eval com is at most M |F| + error PC.Eval M where error PC.Eval denotes the soundness error of PC.Eval.

As for communication, PC.Eval com M has size O λ (M ℓ + ℓ ) (for security parameter λ), while naively repeating M times PC.Eval would yield O λ (M ℓ 2 ) communication. See Appendix H for more precise statements about proof sizes.

Putting everything together. We have shown that the BaseFold commitment PC with individual openings Eval can be compiled into a protocol PC R q for polynomials in R q [X]. The commitment itself consists in committing to each component Φ ij (f ) with Basefold over R ij . A batched opening Eval M of M evaluations

<!-- page 30 -->

at arbitrary points in R q can be obtained from L + 1 executions of PC.Eval com Mk (each in a field R ij ) and L + 1 sumchecks needed in the reduction from Eval com Mk to Eval M k , as shown in the diagram below (where the second arrow is Figure 3 and the first one was explained in Batching on isomorphic components):

PC R q .Eval M ← {PC i .Eval M k } i∈[L+1] ← {PC i .Eval com M k + 1 sumcheck} i∈[L+1]

k−1 The soundness error is (L+1)( 2ℓ+M +error PC.Eval ), where error PC.Eval is an min{p i } d upper bound for the soundness error of Basefold. The communication complexity is O λ (M kLℓ+Lℓ 2 ). In contrast, using PC.Eval openings for individual statements in each of the Lk components would yield O λ (M kLℓ 2 ) communication.

Implementation and Evaluation

We first implemented our proposals over the verifiable HE framework of [CCC + 25] 10 , which we later integrated into the vfhe library [CCC + 26a] for better performance and reproducibility. This full version of the paper considers the updated implementation, and the code reproducing our results is available at https: //github.com/vfhe/Batch-Pack-and-Prove. Results for the previous implementation are presented in the printed version [CCC + 26b]. We follow a similar approach to [CCC + 25] when analyzing performance. In particular, the performance of their approach is dominated by common proof operations, such as the sumcheck and polynomial commitment procedures, which they benchmark over their “proof-friendly” CKKS implementation. For fair comparison, we perform a similar analysis, in the same ring, with the same HE parameters. We run all experiments on an r7i.metal-48xl instance on AWS (Intel Xeon 8488C at 3.2GHz).

8.1

BatchFold

Our first improvement over [CCC + 25] is the change of PC scheme from Brakedown to Basefold, and in particular to our new BatchFold variant. Basefold commitments are asymptotically more expensive than Brakedown (quasilinear √ instead of linear) but they have logarithmic-time verification (instead of O( 2 ℓ )). Thanks to our new techniques (notably packing and the use of H q ), many polynomials we commit to in our protocols are a factor O(N ) smaller than in [CCC + 25], allowing the prover to bear the extra costs of quasilinear proving time, in exchange for significantly faster verification. BatchFold improves performance over Basefold not only for the verifier, but also for the prover computing evaluation proofs, as Figure 5 shows. These measurements include the Merkle commitments, where BatchFold also helps, since it hashes significantly less information. Comparisons between plain Basefold and Brakedown can be found in [ZCF24]. As additional contribution, we implement an estimator for computing optimal parameters for BaseFold and BatchFold.

Available at https://github.com/vfhe/proof-friendly-CKKS (commit e44d520)

<!-- page 31 -->

Commit Basefold eval Batchfold eval

2 17

2 15

Time (ms)

2 13

2 11

Input Size (log 2 )

Basefold Batchfold

2 10

Proof Size (MiB)

2 9

2 8

Input Size (log 2 )

Fig. 5: Basefold [ZCF24] and Batchfold (our work) for R q with N = 2 13 and 3 RNS components. Time is single-threaded and includes the Merkle hashing. We consider only the batching of N/4 components in R q .

We achieve an up to 2.8× performance improvement upon Basefold for evaluation proofs, while proof size is reduced by up to a factor of 9.5×. Our impact to high level protocols could, however, be much greater than this, as our results are only considering the batching of the N/4 = 2 11 CRT components of R q while high level protocols could also batch evaluations of multiple different multivariate polynomials. Compared to [CCC + 25], which takes 8.5 seconds per CRT component of R q (i.e., for each R i,j ) for input size 2 16 using the original implementation of Brakedown, we achieve improvements of up to 302×, taking just 57.7 seconds for the same instance. [CCC + 25] also presents an improved version of Brakedown, but they do not report proof size and proving time for it. Although potential improvements from the optimized version in [CCC + 25] should be taken into consideration, we are only measuring single-threaded time, while [CCC + 25] uses up to 48 threads. Therefore, we expect our results and improvements to hold up, improvements to [CCC + 25] notwithstanding.

8.2

High-level applications

For the polynomial commitment, we provided a direct comparison between ours and [ZCF24,CCC + 25] based on a generic polynomial; however, demonstrating our broader contributions to verifiable computation requires a less generic benchmark. In particular, while [CCC + 25] showcases a microbenchmark based on a single CKKS multiplication, we go significantly beyond this and consider small HE applications. We consider 3 small generic neural network models, each composed of 2 fully-connected hidden layers using f (x) = x 2 as the activation function. We denote our models by tuples (n 0 , n 1 ), representing the number of neurons in the hidden layers. All models take 30 inputs, and have 2 outputs – thus being suitable in small classification problems (e.g., [WMSS93,K + 96]).

<!-- page 32 -->

We consider batched evaluations using CKKS’s SIMD packing [CKKS17] (i.e., N/2 = 2 12 samples are classified at once) and present the detailed architecture in Appendix I. We note that our goal is to demonstrate the feasibility of our vHE approach, and that machine learning optimization aspects are out of our scope. We compile these small HE applications into our R CKKS relations – composed of GKR circuits and range checks – and compute precisely the number of wires, gates and commitments needed to evaluate and prove them. From those, we measure the range proofs end to end, and estimate the other components from measurements of their building blocks: we consider the execution times for polynomial commitment operations given in Section 8.1, and we implement and benchmark SumChecks, following [CCC + 25].

Arithmetic circuit. In [CCC + 25] the performance analysis focuses on the range proof protocol Π range , under the assumption that Π AC and the actual HE and GKR evaluations add negligibly to the overall cost of the protocol. Our estimates confirm that the GKR evaluation costs are indeed very small, taking 21.9, 5.9, and 3.0 seconds for our three circuits, respectively. On the other hand, Π AC should also prove the evaluations of large sparse polynomials that describe the circuit, an aspect overlooked by [CCC + 25] and left to be handled through generic techniques. In this work, we improve Π AC in two ways. First, thanks to our refined arithmetization we minimize the numbers of polynomials encoding the circuit structure that have to be proven. Second, we propose the SparsePack PIOP specialized to prove the evaluation of these sparse polynomials. Therefore, in our evaluation below we focus on comparing these two components, sparse commitments and range proofs.

Sparse commitments. We compare the performance of SparsePack with that of using Spark [Set20,STW24]. Our benchmark are the evaluations of the sparse polynomials arising from the HE circuits corresponding to the three neural networks mentioned earlier. Table 2 presents our results. We are able to reduce proof sizes by more than an order of magnitude. Execution time is also improved by factors of 10–23×. A large benefit of our construction is that it does not require any commitments at run time – all our commitments depend only on the circuit and not on the inputs, enabling them to be precomputed. Notice that most of the cost of our solution comes from SumChecks, which could be trivially parallelized. Appendix G further discusses and details the operations required by each solution. We emphasize that here we are not comparing our solution with an application of Spark [Set20,STW24] to handle the sparse polynomials encoding the circuit wiring in [CCC + 25]. Such a comparison would likely show even further improvements for us since the arithmetization of [CCC + 25] requires more sparse polynomials (and with more variables) than in our case (see Section 5).

Range proofs. Compared to [CCC + 25], our strategy of packing and working over H q enables improvements of O(N/d) times in both proof size and performance. We measure execution times of 5m54s, 2m47s, and 1m24s, respectively for each of our range of our three circuits above, with the optimized variant Π̂ range

<!-- page 33 -->

Table 2: Performance of our SparsePack and comparison with Spark. Notice that our solution does not require execution-time commitments.

Spark SparsePack SumCheck Comm. Eval SumCheck Eval Size Time Time Size Time Size Time Size Time (128, 64) 235.3 MiB 6m14s 9m38s 6.2 GiB 6m35s 25.4 KiB 1s 163.0 MiB 2m6s (64, 16) 176.5 MiB 1m33s 2m8s 5.5 GiB 1m37s 17.7 KiB 1s 159.4 MiB 13s (32, 16) 150.3 MiB 47s 58s 5.2 GiB 48s 16.7 KiB 1s 159.4 MiB 13s

Model (n 0 , n 1 )

proof that takes H q = F p (Fig. 10; parameters σ = 2 11 , m = 15, κ = 20, Appendix D.5). Appendix I.2 details our results. It is difficult to precisely estimate the costs for [CCC + 25], since their protocol is unlikely to handle the circuits of our benchmark without unrealistic amounts of memory (given the O(N ) overhead of their range proof, discussed in Section 4). Even if possible, [CCC + 25] estimates 25 seconds per multiplication, leading to a proof time of at least 1 hour 20 minutes for our largest circuit, which contains 192 multiplications. For the same circuit, our range proof takes less than 6 minutes. Additionally, their results are for multithreaded execution with up to 48 threads, whereas we are reporting only single-threaded execution time. Considering this, our wall-clock improvement of more than 13× would likely translate to more than 100× times in computational time.

Discussion on concrete verifier costs. Our experimental evaluation focuses on the concrete performance of the prover, which is often regarded as the major challenge in verifiable HE with sublinear verification, and leaves the implementationlevel analysis of the verifier as future work. The vfhe library provides timings for the verification of our building blocks. For example, a Basefold (resp. Batch- Fold) evaluation proof over R q verifies in 0.4–1.7 s (resp. 0.2–0.3 s) for 2 8 to 2 16 entries, and the range proof of Table 3 at its largest size, 2 24 digits, takes 1.8 s, single-threaded. The full verification of our IOPs, however, would require procedures beyond the verification of the building blocks, and extrapolating these timings is difficult. We nevertheless remark that, asymptotically, our protocol achieves polylogarithmic verification time in the circuit size, improving over the square-root verification complexity of [CCC + 25]. This asymptotic improvement suggests that our approach is fundamentally more scalable and that, for sufficiently large computations, verification costs can be amortized and be faster than trivial solutions, such as recomputing the circuit. Moreover, recomputation is not always the appropriate baseline in applications of verifiable FHE. In some scenarios, the verifier may not have access to the prover’s inputs and therefore cannot independently recompute. An example is privacy-preserving ML, where a server holding a proprietary model evaluates encrypted client queries. As a future direction, our protocols could be extended to this scenario by using circuit privacy [Gen09] and a zero-knowledge version of our proof system. We expect this to work based on standard techniques. For the former, one may either rely on noise flood-

<!-- page 34 -->

ing [Gen09] or recent proposals, such as Differential-Privacy-based circuit privacy for CKKS [HMSS25,KS25], which are concretely more efficient. Regarding ZK, the conversion can be achieved through the zero-knowledge sumcheck of Libra [XZZ + 19] and PCs with ZK evaluation arguments.

Acknowledgements We would like to thank the anonymous reviewers of Asiacrypt 2026 for the insightful comments and discussions that allowed us to improve the presentation in Section 2.3 and our results in Section 5. This work is partially funded by the grants PID2022-142290OB-I00, JDC2022-049711-I, JDC2024-055789-I, and CEX2024-001471-M, funded by MCIN/AEI/10.13039/501100011033/ FEDER, UE and ESF+, and it is part of the PICOCRYPT project that has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (Grant agreement No. 101001283), and of the VERIFHE project funded by the European Union (GA: 101287502). Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council. Neither the European Union nor the granting authority can be held responsible for them.

## References

ABMP24. Andreea Alexandru, Ahmad Al Badawi, Daniele Micciancio, and Yuriy Polyakov. Application-aware approximate homomorphic encryption: Configuring FHE for practical use. Cryptology ePrint Archive, Paper 2024/203, 2024. ACGS23. Diego F. Aranha, Anamaria Costache, Antonio Guimarães, and Eduardo Soria-Vazquez. HELIOPOLIS: Verifiable computation over homomorphically encrypted data from interactive oracle proofs is practical. Cryptology ePrint Archive, Paper 2023/1949, 2023. AHKS22. Amin Abdulrahman, Vincent Hwang, Matthias J. Kannwischer, and Amber Sprenkels. Faster Kyber and Dilithium on the Cortex-M4. In Giuseppe Ateniese and Daniele Venturi, editors, Applied Cryptography and Network Security, pages 853–871, Cham, 2022. Springer International Publishing. APS15. Martin R Albrecht, Rachel Player, and Sam Scott. On the concrete hardness of learning with errors. Journal of Mathematical Cryptology, 9(3):169– 203, 2015. BCFK21. Alexandre Bois, Ignacio Cascudo, Dario Fiore, and Dongwoo Kim. Flexible and efficient verifiable computation on encrypted data. In Juan Garay, editor, PKC 2021: 24th International Conference on Theory and Practice of Public Key Cryptography, Part II, volume 12711 of Lecture Notes in Computer Science, pages 528–558, Virtual Event, May 10–13, 2021. Springer, Cham, Switzerland. BFS20. Benedikt Bünz, Ben Fisch, and Alan Szepieniec. Transparent SNARKs from DARK compilers. In Anne Canteaut and Yuval Ishai, editors, Advances in Cryptology – EUROCRYPT 2020, Part I, volume 12105 of Lecture Notes in Computer Science, pages 677–706, Zagreb, Croatia, May 10– 14, 2020. Springer, Cham, Switzerland.

<!-- page 35 -->

CBBZ23.

Binyi Chen, Benedikt Bünz, Dan Boneh, and Zhenfei Zhang. Hyper- Plonk: Plonk with linear-time prover and high-degree custom gates. In Carmit Hazay and Martijn Stam, editors, Advances in Cryptology – EU- ROCRYPT 2023, Part II, volume 14005 of Lecture Notes in Computer Science, pages 499–530, Lyon, France, April 23–27, 2023. Springer, Cham, Switzerland. CCC + 25. Ignacio Cascudo, Anamaria Costache, Daniele Cozzo, Dario Fiore, Antonio Guimarães, and Eduardo Soria-Vazquez. Verifiable computation for approximate homomorphic encryption schemes. In Yael Tauman Kalai and Seny F. Kamara, editors, Advances in Cryptology – CRYPTO 2025, Part VII, volume 16006 of Lecture Notes in Computer Science, pages 643–677, Santa Barbara, CA, USA, August 17–21, 2025. Springer, Cham, Switzerland. CCC + 26a. Ignacio Cascudo, Anamaria Costache, Daniele Cozzo, Adrien Dubois, Dario Fiore, Antonio Guimarães, Robin Köstler, Michał Osadnik, Alin-Petru Ros , u, and Eduardo Soria-Vazquez. The vfhe library. https://github. com/vfhe/vfhe, 2026. Commit 769198d. CCC + 26b. Ignacio Cascudo, Anamaria Costache, Daniele Cozzo, Dario Fiore, Antonio Guimarães, and Eduardo Soria-Vazquez. Batch, pack, and prove: More efficient verifiable computation for ckks. In ASIACRYPT 2026, 2026. CCH + 19. Ran Canetti, Yilei Chen, Justin Holmgren, Alex Lombardi, Guy N. Rothblum, Ron D. Rothblum, and Daniel Wichs. Fiat-Shamir: from practice to theory. In Moses Charikar and Edith Cohen, editors, 51st Annual ACM Symposium on Theory of Computing, pages 1082–1090, Phoenix, AZ, USA, June 23–26, 2019. ACM Press. CCKP19. Shuo Chen, Jung Hee Cheon, Dongwoo Kim, and Daejun Park. Verifiable computing for approximate computation. Cryptology ePrint Archive, Report 2019/762, 2019. + CCP 24. Jung Hee Cheon, Hyeongmin Choe, Alain Passelègue, Damien Stehlé, and Elias Suvanto. Attacks against the IND-CPA D security of exact FHE schemes. In Bo Luo, Xiaojing Liao, Jun Xu, Engin Kirda, and David Lie, editors, ACM CCS 2024: 31st Conference on Computer and Communications Security, pages 2505–2519, Salt Lake City, UT, USA, October 14–18, 2024. ACM Press. CKKS17. Jung Hee Cheon, Andrey Kim, Miran Kim, and Yong Soo Song. Homomorphic encryption for arithmetic of approximate numbers. In Tsuyoshi Takagi and Thomas Peyrin, editors, Advances in Cryptology – ASIACRYPT 2017, Part I, volume 10624 of Lecture Notes in Computer Science, pages 409–437, Hong Kong, China, December 3–7, 2017. Springer, Cham, Switzerland. CMS19. Alessandro Chiesa, Peter Manohar, and Nicholas Spooner. Succinct arguments in the quantum random oracle model. In Dennis Hofheinz and Alon Rosen, editors, TCC 2019: 17th Theory of Cryptography Conference, Part II, volume 11892 of Lecture Notes in Computer Science, pages 1–29, Nuremberg, Germany, December 1–5, 2019. Springer, Cham, Switzerland. FGP14. Dario Fiore, Rosario Gennaro, and Valerio Pastro. Efficiently verifiable computation on encrypted data. In Gail-Joon Ahn, Moti Yung, and Ninghui Li, editors, ACM CCS 2014: 21st Conference on Computer and Communications Security, pages 844–855, Scottsdale, AZ, USA, November 3–7, 2014. ACM Press.

<!-- page 36 -->

FNP20.

Dario Fiore, Anca Nitulescu, and David Pointcheval. Boosting verifiable computation on encrypted data. In Aggelos Kiayias, Markulf Kohlweiss, Petros Wallden, and Vassilis Zikas, editors, PKC 2020: 23rd International Conference on Theory and Practice of Public Key Cryptography, Part II, volume 12111 of Lecture Notes in Computer Science, pages 124–154, Edinburgh, UK, May 4–7, 2020. Springer, Cham, Switzerland. Mariana Gama, Emad Heydari Beni, Jiayi Kang, Jannik Spiessens, and Frederik Vercauteren. Blind zkSNARKs for private proof delegation and verifiable computation over encrypted data. Cryptology ePrint Archive, Report 2024/1684, 2024. Craig Gentry. Fully homomorphic encryption using ideal lattices. In Michael Mitzenmacher, editor, 41st Annual ACM Symposium on Theory of Computing, pages 169–178, Bethesda, MD, USA, May 31 – June 2, 2009. ACM Press. Sanjam Garg, Aarushi Goel, and Mingyuan Wang. How to prove statements obliviously? In Leonid Reyzin and Douglas Stebila, editors, Advances in Cryptology – CRYPTO 2024, Part X, volume 14929 of Lecture Notes in Computer Science, pages 449–487, Santa Barbara, CA, USA, August 18–22, 2024. Springer, Cham, Switzerland. Shafi Goldwasser, Yael Tauman Kalai, and Guy N. Rothblum. Delegating computation: interactive proofs for muggles. In Richard E. Ladner and Cynthia Dwork, editors, 40th Annual ACM Symposium on Theory of Computing, pages 113–122, Victoria, BC, Canada, May 17–20, 2008. ACM Press. Alexander Golovnev, Jonathan Lee, Srinath T. V. Setty, Justin Thaler, and Riad S. Wahby. Brakedown: Linear-time and field-agnostic SNARKs for R1CS. In Helena Handschuh and Anna Lysyanskaya, editors, Advances in Cryptology – CRYPTO 2023, Part II, volume 14082 of Lecture Notes in Computer Science, pages 193–226, Santa Barbara, CA, USA, August 20– 24, 2023. Springer, Cham, Switzerland. Chaya Ganesh, Anca Nitulescu, and Eduardo Soria-Vazquez. Rinocchio: SNARKs for ring arithmetic. Journal of Cryptology, 36(4):41, October 2023. Qian Guo, Denis Nabokov, Elias Suvanto, and Thomas Johansson. Key recovery attacks on approximate homomorphic encryption with non-worstcase noise flooding countermeasures. In Davide Balzarotti and Wenyuan Xu, editors, USENIX Security 2024: 33rd USENIX Security Symposium, Philadelphia, PA, USA, August 14–16, 2024. USENIX Association. Intak Hwang, Seonhong Min, Jinyeong Seo, and Yongsoo Song. On the security and privacy of CKKS-based homomorphic evaluation protocols. In Goichiro Hanaoka and Bo-Yin Yang, editors, Advances in Cryptology – ASIACRYPT 2025, Part VII, volume 16251 of Lecture Notes in Computer Science, pages 296–330, Melbourne, VIC, Australia, December 8–12, 2025. Springer, Singapore, Singapore. Mi-Ying Miryam Huang, Xinyu Mao, and Jiapeng Zhang. Sublinear proofs over polynomial rings. Cryptology ePrint Archive, Report 2025/199, 2025. Syed Mahbub Hafiz, Bahattin Yildiz, Marcos A. Simplício Jr., Thales B. Paiva, Henrique S. Ogawa, Gabrielle De Micheli, and Eduardo Lopes Cominetti. Incompleteness in number-theoretic transforms: New tradeoffs and faster lattice-based cryptographic applications. In 2024 IEEE Euro-

GBK + 24.

Gen09.

GGW24.

GKR08.

GLS + 23.

GNS23.

GNSJ24.

HMSS25.

HMZ25.

HYS + 25.

<!-- page 37 -->

pean Symposium on Security and Privacy, pages 565–584, Venice, Italy, June 30 – July 4, 2025. IEEE Computer Society Press. Jae Hyung Ju, Jaiyoung Park, Jongmin Kim, Minsik Kang, Donghwan Kim, Jung Hee Cheon, and Jung Ho Ahn. NeuJeans: Private neural network inference with joint optimization of convolution and FHE bootstrapping. In Bo Luo, Xiaojing Liao, Jun Xu, Engin Kirda, and David Lie, editors, ACM CCS 2024: 31st Conference on Computer and Communications Security, pages 4361–4375, Salt Lake City, UT, USA, October 14–18, 2024. ACM Press. Ron Kohavi et al. Scaling up the accuracy of naive-bayes classifiers: A decision-tree hybrid. In Kdd, volume 96, pages 202–207, 1996. Jaehyung Kim. Efficient homomorphic integer computer from CKKS. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2025(4):873–898, 2025. Kamil Kluczniak and Giacomo Santato. On circuit private, multikey and threshold approximate homomorphic encryption. IACR Communications in Cryptology (CiC), 2(1):9, 2025. Christian Knabenhans, Alexander Viand, and Anwar Hithnawi. Towards robust fhe for the real world. Real World Crypto 2024, 2024. Carsten Lund, Lance Fortnow, Howard J. Karloff, and Noam Nisan. Algebraic methods for interactive proof systems. In 31st Annual Symposium on Foundations of Computer Science, pages 2–10, St. Louis, MO, USA, October 22–24, 1990. IEEE Computer Society Press. Baiyu Li and Daniele Micciancio. On the security of homomorphic encryption on approximate numbers. In Anne Canteaut and François-Xavier Standaert, editors, Advances in Cryptology – EUROCRYPT 2021, Part I, volume 12696 of Lecture Notes in Computer Science, pages 648–677, Zagreb, Croatia, October 17–21, 2021. Springer, Cham, Switzerland. Vadim Lyubashevsky and Gregor Seiler. NTTRU: Truly fast NTRU using NTT. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2019(3):180–201, 2019. Tianyi Liu, Xiang Xie, and Yupeng Zhang. zkCNN: Zero knowledge proofs for convolutional neural network predictions and accuracy. In Giovanni Vigna and Elaine Shi, editors, ACM CCS 2021: 28th Conference on Computer and Communications Security, pages 2968–2985, Virtual Event, Republic of Korea, November 15–19, 2021. ACM Press. Ngoc Khanh Nguyen, George O’Rourke, and Jiapeng Zhang. Hachi: Efficient lattice-based multilinear polynomial commitments over extension fields. Cryptology ePrint Archive, Paper 2026/156, 2026. Srinath Setty. Spartan: Efficient and general-purpose zkSNARKs without trusted setup. In Daniele Micciancio and Thomas Ristenpart, editors, Advances in Cryptology – CRYPTO 2020, Part III, volume 12172 of Lecture Notes in Computer Science, pages 704–737, Santa Barbara, CA, USA, August 17–21, 2020. Springer, Cham, Switzerland. Srinath Setty and Jonathan Lee. Quarks: Quadruple-efficient transparent zkSNARKs. Cryptology ePrint Archive, Report 2020/1275, 2020. Srinath T. V. Setty, Justin Thaler, and Riad S. Wahby. Unlocking the lookup singularity with Lasso. In Marc Joye and Gregor Leander, editors, Advances in Cryptology – EUROCRYPT 2024, Part VI, volume 14656 of Lecture Notes in Computer Science, pages 180–209, Zurich, Switzerland, May 26–30, 2024. Springer, Cham, Switzerland.

JPK + 24.

K + 96.

Kim25.

KS25.

KVH24.

LFKN90.

LM21.

LS19.

LXZ21.

NOZ26.

Set20.

SL20.

STW24.

<!-- page 38 -->

Tha13.

Justin Thaler. Time-optimal interactive proofs for circuit evaluation. In Ran Canetti and Juan A. Garay, editors, Advances in Cryptology – CRYPTO 2013, Part II, volume 8043 of Lecture Notes in Computer Science, pages 71–89, Santa Barbara, CA, USA, August 18–22, 2013. Springer Berlin Heidelberg, Germany. VKH23. Alexander Viand, Christian Knabenhans, and Anwar Hithnawi. Verifiable fully homomorphic encryption, 2023. VSBW13. Victor Vu, Srinath T. V. Setty, Andrew J. Blumberg, and Michael Walfish. A hybrid architecture for interactive verifiable computation. In 2013 IEEE Symposium on Security and Privacy, pages 223–237, Berkeley, CA, USA, May 19–22, 2013. IEEE Computer Society Press. WMSS93. William Wolberg, Olvi Mangasarian, Nick Street, and W. Street. Breast Cancer Wisconsin (Diagnostic). UCI Machine Learning Repository, 1993. DOI: https://doi.org/10.24432/C5DW2B. XZZ + 19. Tiancheng Xie, Jiaheng Zhang, Yupeng Zhang, Charalampos Papamanthou, and Dawn Song. Libra: Succinct zero-knowledge proofs with optimal prover computation. In Alexandra Boldyreva and Daniele Micciancio, editors, Advances in Cryptology – CRYPTO 2019, Part III, volume 11694 of Lecture Notes in Computer Science, pages 733–764, Santa Barbara, CA, USA, August 18–22, 2019. Springer, Cham, Switzerland. ZCF24. Hadas Zeilberger, Binyi Chen, and Ben Fisch. BaseFold: Efficient field-agnostic polynomial commitment schemes from foldable codes. In Leonid Reyzin and Douglas Stebila, editors, Advances in Cryptology – CRYPTO 2024, Part X, volume 14929 of Lecture Notes in Computer Science, pages 138–169, Santa Barbara, CA, USA, August 18–22, 2024. Springer, Cham, Switzerland. ZLW + 21. Jiaheng Zhang, Tianyi Liu, Weijie Wang, Yinuo Zhang, Dawn Song, Xiang Xie, and Yupeng Zhang. Doubly efficient interactive proofs for general arithmetic circuits with linear prover time. In Giovanni Vigna and Elaine Shi, editors, ACM CCS 2021: 28th Conference on Computer and Communications Security, pages 159–177, Virtual Event, Republic of Korea, November 15–19, 2021. ACM Press.

A

Additional Preliminaries

PIOP Efficiency. We consider the following efficiency metrics: prover’s (resp. verifier’s) running time T P (resp. T V ); number of rounds r; number of oracles sent by the prover o; size s of the proof oracles (i.e., the sum of length of all the polynomials sent by the prover); number of verifier’s queries q to the oracles.

A.1

Polynomial Commitments with Batched Evaluations

Definition 5 (Multilinear Polynomial Commitment). A polynomial commitment scheme for multilinear polynomials over a ring R is a tuple PC = (Setup, Com, VerCom, , ProveEval, VerEval)

Setup(1 λ , ℓ) → (ck, vk) takes the security parameter and (possibly) an upper bound on the number of variables ℓ, and outputs a commitment key ck and a verification key vk.

<!-- page 39 -->

Com(ck, f ) → (cm f , opn f ) takes a multilinear polynomial f ∈ R (≤1) [X 1 , . . . , X ℓ ], and outputs a commitment cm f and an opening opn f . VerCom(vk, cm f , f, opn f ) → b checks if opn f is a valid opening for the commitment cm f to a polynomial f , by accepting (b = 1) or not (b = 0). ⟨ProveEval(ck, cm f , a, y, ℓ; f, opn f ), VerEval(vk, cm f , a, y, ℓ)⟩ → b is a protocol in which the prover ProveEval aims to convince the verifier VerEval that y = f (a) for the polynomial f ∈ R (≤1) [X 1 , . . . , X ℓ ] committed in cm f . As a shorthand we write Eval to refer to ⟨ProveEval, VerEval⟩.

Correctness. PC is correct if for any multilinear ℓ-variate polynomial f (ck, vk) ← Setup(1 λ , ℓ) = 1. Pr VerCom(vk, cm f , f, opn f ) = 1 (cm f , opn f ) ← Com(ck, f )

Binding. PC is computationally binding if for all PPT adversaries Adv the following probability is negl(λ):

 VerCom(vk, cm, f, opn f ) = 1 λ (ck, vk) ← Setup(1 , ℓ)  Pr  ∧VerCom(vk, cm, f ′ , opn ′ f ) = 1 (cm, f, opn f , f ′ , opn ′ f ) ← Adv(ck) ∧f ̸ = f



Knowledge Soundness. We say that PC is knowledge-sound if ⟨ProveEval, VerEval⟩ is a complete and knowledge-sound argument of knowledge for the NP relation R Eval = {( x = (cm f , a, y, ℓ); w = (f, opn f ))} of tuples such that

f ∈ R (≤1) [X 1 , . . . , X ℓ ] ∧ y = f (a) ∧ VerCom(vk, cm f , f, opn f ) = 1

Succinctness. We say that PC is succinct if the commitments produced by Com have size sublinear in the size of a polynomial and if ⟨ProveEval, VerEval⟩ is a succinct argument.

A.2

Compiling PIOPs into SNARKs

Given a multilinear polynomial commitment it is possible to turn a PIOP for a relation R into a public-coin interactive argument of knowledge for the same relation. The compilation consists in two steps: replace every oracle sent by the prover with a commitment to the underlying polynomial, and replace every verifier’s query to an oracle JpK at a point a with sending the actual value p(a) and proving its correctness w.r.t. the commitment of p by using the ⟨ProveEval, VerEval⟩ protocol. To this standard compilation technique we add the observation that if we start from a PIOP for an oracle relation R then we can easily build a (preprocessing) commit-and-prove argument. Finally, if the PIOP is public-coin so is the resulting argument system and thus it can be further compiled into a non-interactive argument using the Fiat-Shamir transform. We summarize the compiler in the following theorem whose proof follows from previous work, e.g., [BFS20].

<!-- page 40 -->

Theorem 3. Let PC be a multilinear polynomial commitment scheme and let Π be a PIOP for an oracle relation R over tuples ( i , x , w ) = ({Jp i j K} j , {Jp x i K} i , ({p i j } j , {p x i } i )) with negligible soundness error. There exists a public-coin interactive argument for the commit-and-prove relation

R ′ = {( i ′ , x ′ , w ′ ) =

({cm i j } j , {cm x i } i , ({p x i , opn x i } i {Jp i j K} j , {Jp x i K} i , ({p i j } j , {p x i } i ))) ∈ R ^ VerCom(vk, cm x i , p x i , opn x i ) = 1

i

where all the commitments cm i j = Com(ck, p i j ) are honestly computed in the preprocessing phase.

The efficiency of the resulting argument depends on the efficiency of both Π and PC as follows. For Π, let T P and T V be its prover and verifier running times, and let r, q, o, s be, respectively, its round complexity, number of verifier’s queries, number of prover’s oracles, and total size of the oracles. For PC, let T Com , T ProveEval , T VerEval be the running times of the corresponding algorithms, and let |cm| and |π PC | be the size of a commitment and a proof respectively.

- Proving time is T P + T Com · s + T ProveEval · q - Verifier time is T V + T VerEval · q - Proof size is |cm| · o + |π PC | · q

In our work, we use a straightforward extension of this compilation that relies on PCs with batched evaluation proofs in order to prove all the evaluation proofs involve in the PIOP with single proof. Assume that the proving time (resp. proof size) of batching is a function T ProveEval (·) (resp. S π (·)) of the batch size. Then we get the following efficiency:

- Proving time is T P + T Com · s + T ProveEval (q) - Verifier time is T V + T VerEval · q - Proof size is |cm| · o + S π (q)

A.3

Round-by-Round Soundness

We recall the notions of round-by-round (RBR) soundness [CCH + 19] and roundby-round knowledge [CMS19] for PIOPs. These notions are useful to precisely argue the knowledge-soundness error of the SNARK obtained after applying the Fiat-Shamir transformation. Informally, a RBR sound protocol has a well-defined state (accept or reject) at each round and, if it starts with a false statement, at each round there should be a negligible probability of turning from a reject to an accept state.

Definition 6 (Round-by-Round Soundness [CCH + 19]). A PIOP Π for an indexed oracle relation R satisfies round-by-round (RBR) soundness with error δ if there exists a state function state( i , x , tr) such that:

<!-- page 41 -->

- If ( i , x ) ∈ / L R then state( i , x , ∅) = 0, - For any ( i , x ) and any complete transcript ( i , x , tr), if state( i , x , tr) = 0 then V( i , x , tr) rejects. - If ( i , x , tr) is a partial transcript such that state( i , x , tr) = 0, then for every potential prover’s message π, holds that Pr[state( i , x , tr|π|c) = 1 : c ← $ V( i , x , tr|π)] ≤ δ.

Definition 7 (Round-by-Round Knowledge [CMS19]). A PIOP Π for an indexed oracle relation R satisfies round-by-round (RBR) knowledge with error δ if there exists a polynomial-time extractor Ext and a state function state( i , x , tr) such that:

- state( i , x , ∅) = 0, - For any ( i , x ) and any complete transcript ( i , x , tr), if state( i , x , tr) = 0 then V( i , x , tr) rejects. - If ( i , x , tr) is a partial transcript such that state( i , x , tr) = 0, if Pr[state( i , x , tr|π|c) = 1 : c ← $ V( i , x , tr|π)] > δ, then ( i , x , Ext( i , x , tr|π)) ∈ R.

It is possible to see that an analogous version of Lemma 2 can be stated for RBR soundness and RBR knowledge.

Lemma 6. Consider a δ-RBR-sound PIOP for oracle relations R such that for all ( i , x , w ) ∈ R w consists only of polynomials such that the statement contains oracles to these polynomials. The PIOP has δ-RBR-knowledge and the extractor runs in time O(| w |).

The proof, in particular the construction of the extractor, is essentially the same as in the proof of Lemma 2 (see [CBBZ23]). The only difference is that we have to define the state function for round-by-round knowledge, which can be define equal to the state function of RBR-soundness, except that on empty transcripts it always rejects, regardless of whether the statement is in the language.

RBR soundness is particularly useful to understand the (RBR) soundness guarantees of protocols that need parallel repetitions. This is summarized by the result [CCH + 19, Corollary 5.7], restated here for PIOPs.

Theorem 4. Suppose that Π is a 2r-round PIOP with δ-soundness. Then, its κ-parallel repetition Π κ is δ κ -sound and δ κ/r -RBR-sound.

A.4

The Sumcheck Protocol

Below we describe Π sum as either an interactive proof or a PIOP. In our protocols, V might not be given (oracle access to) p(r 1 , . . . , r ℓ ) directly, but rather enough information to compute that on its own. For example, for p = f g + h, where V knows f , it might be given (oracle access to) g(r 1 , . . . , r ℓ ) and h(r 1 , . . . , r ℓ ).

<!-- page 42 -->

PIOP Π usum for ((y, Jp̃K); p̃) ∈ R usum

P and V run the PIOP Π sum for ((y, JũK); ũ) ∈ R usum with ũ = unpack(p̃). Given Π sum .V’s query to JũK on r = (r 1 , r 2 ), Π usum .V makes a query to Jp̃K on r 1 and given its answer v = p̃(r 1 ), returns uEval(v, r 2 ) to Π sum .V.

Figure 6: PIOP for R usum

The sum-check protocol/PIOP Π sum for R sum

for j = 1 to ℓ

P

P computes and sends g j (X) ←

V sends r j ← $ Ŝ N . P sends p(r 1 , . . . , r ℓ ).

i∈{0,1} ℓ−j p(r 1 , . . . , r j−1 , X, i).

(In the PIOP version: V queries JpK on (r 1 , . . . , r ℓ )).

V accepts if the following checks are satisfied:

∀j ∈ [ℓ] : g j−1 (r j−1 ) = g j (0) + g j (1), where g 0 (r 0 ) = y

g ℓ (r ℓ ) = p(r 1 , . . . , r ℓ )

Theorem 5. Let Ŝ N ⊆ R be an exceptional set. The PIOP for R sum described above has perfect completeness and δ-knowledge-soundness with δ = dℓ/| Ŝ N |.

⊔ ⊓

Proof. It follows from the soundness analysis in [CCKP19] and Lemma 2.

Unpacked Sumcheck We define the unpacked P sumcheck oracle relation R usum as the set of tuples ((y, Jp̃K); p̃) such that y = b∈{0,1} ℓ ,k∈{0,1} ν p̃(b)[k], or equivalently,

R usum = {((y, Jp̃K); p̃) : ((y, Junpack(p̃)K); unpack(p̃)) ∈ R sum }.

Given the above reduction of R usum to R sum we can construct a PIOP Π usum for R usum using the PIOP Π sum for R sum , changed so that the verifier samples random challenges in an exceptional set Ŝ 0 ⊂ Z q . Let us call Π sum this variant of Π sum . Π usum simply runs Π sum on the virtual oracle unpack(p̃) and uses uEval to simulate queries to the unpacked oracle.

Theorem 6. Π usum is a PIOP with perfect completeness, prover’s efficiency O(2 ℓ+ν ), verifier’s efficiency O(ℓ+2 ν ), δ usum -knowledge soundness with δ usum = (ℓ + ν)/| Ŝ 0 |, and RBR-knowledge with error 1/| Ŝ 0 |.

The theorem follows by specializing known results for the sumcheck protocol to the case of challenges in the smaller set Ŝ 0 . When Ŝ 0 is not large enough to have 1/| Ŝ 0 | negligible, we repeat Π usum κ(ℓ + ν) times in parallel, obtaining RBR-knowledge error 1/| Ŝ 0 | κ which is negligible for large enough κ [CCH + 19].

<!-- page 43 -->

A.5

CKKS

We recall the proof-friendly CKKS construction, as presented in [CCC + 25]. Note that the secret and public key generation algorithms, as well as the encryption, addition and multiplication algorithms are unchanged. For a full description of the “regular” CKKS scheme, we point the reader to [CKKS17]. For ease of exposition, we mostly follow the notation of [CCC + 25]. Let q 0 < q 1 < · · · < q L be the chain of moduli as outlined in the preliminaries and (ω 0 , ω 1 , . . . , ω L ) their respective CRT bases, χ key be the secret key distribution, and χ err , χ enc be the error and encryption distributions, respectively.

CRT Let l denote l = L − j, and ω j = (p 0 , p 1 , . . . , p l ) be a CRT base for q j . Given a ∈ R q 0 , the inverse CRT map is defined as follows: l+1 := , . . . , [a] , [a] CRT −1 (a) [a] ω j p l ∈ R q 0 . p 1 p 0 Let Q i = q 0 /p i and Q̂ i = (q 0 /p i ) −1 p i be the CRT recomposition constants. The generator of the ideal defining the embedding is defined as z l := P l Q 1, . . . , 1 , 0, . . . , 0) ∈ R q 0 . i=0 i Q̂ i = CRT( | {z }

l+1 times

For each 0 ≤ j ≤ L, the CRT recomposition vector for a given a ∈ R q 0 is: h i h i h i . PW ω l (a) := aQ 0 Q̂ 0 , aQ 1 Q̂ 1 , . . . , aQ l Q̂ l

q 0

Proof-friendly CKKS

q 0

q 0

$

evk ← KeySwitchGen(s, s 2 ): For sk = (1, s), for i = 0, . . . , L, sample a i ← − R q 0 , sample e i ← χ err . Compute b i = −a i · s + e i + PW ω L (s 2 )[i] (mod q 0 ). Recall that l = L − j, for each level j ∈ {0, . . . , L}, compute l+1 evk := (evk j,0 , evk j,1 ) ← ((z l b i ) i=0,...,l , (z l a i ) i=0,...,l ) ∈ R q 2 0 .

µ + e ′ ← Dec(sk, ct): Given a ciphertext ct ∈ R q 0 for some level j, parse (c 0 , c 1 ) = ct. Output the CRT recomposition of the first l = L−j components of ⟨ct, sk⟩, namely CRT ω j (⟨ct, sk⟩).

(d 0 , d 1 , d 2 ) ← PreMult(ct 0 , ct 1 , j): For some level j ∈ {0, . . . , L}, compute

(d 0 , d 1 , d 2 ) := (ct 0 [0] · ct 1 [0], ct 0 [0] · ct 1 [1] + ct 1 [0] · ct 0 [1], ct 0 [1] · ct 1 [1]), (18)

as an element of R q 3 0 . Perform the key switching as follows. ct ← KeySwitch(evk, ct = (d 0 , d 1 , d 2 )): output ct ′ = (c ′ 0 , c ′ 1 ) where

c ′ i := d i + ⟨CRT −1 ω j (d 2 ), evk j,i ⟩ ∈ R q 0 , i = 0, 1.

= [q j+1 /q j ] q j+1 · z l ∈ R q 0 . ct ′′ ← Rescale(ct ′ , j): Let ct ′ = (c ′ 0 , c ′ 1 ), and p −1 l ′′ := ′′ ′′ Rescale is done by computing ct (c 0 , c 1 ) ∈ R q 2 0 as c ′′ i := c ′ i − [c ′ i ] p l p −1 ∈ R q 0 , i = 0, 1. l

<!-- page 44 -->

A modular construction of the PIOP Π CKKS

A.6

Belowe recall how we modularly build a PIOP Π CKKS for the relation R CKKS from PIOPs Π range for R range and Π AC for R AC .

PIOP Π CKKS for ( i , x ; w ) ∈ R CKKS

D−2 u P and V run Π AC for (C, (Jx̃K, JỹK, J w̃ 2 u K, {J w̃ l K} D−2 l=0 ); x, y, w 2 , {w l } l=1 ) ∈ R AC

P and V run Π range for (2 u , J w̃ 2 u K; w 2 u ) ∈ R range and (q L−D+1 /p L−D+1 , JỹK; y) ∈ R range

For l = 0, . . . , D − 2:

P and V run Π range for (q L−l /p L−l , J w̃ l K; w l ) ∈ R range .

B

Auxiliary Material on PIOP for Unpacked Polynomials

B.1

Proof of Theorem 1

Proof. For correctness, we refer to the explanation in Section 3. Prover efficiency follows from the runtime of sumcheck, while Verifier efficiency is the sumcheck’s verification plus the time to compute ψ, ψ ∗ and uEval. P For soundness, if the statement is false, i.e., ∃i : y i ̸ = ũ(x i ), then ỹ(Z, T ) − polynomial, and by generalized Schwartzb∈{0,1} ℓ ′ ũ(b)E(b, Z, T ) is a nonzero P Zippel the probability that ỹ(σ, τ ) = b∈{0,1} ℓ ′ ũ(b)E(b, σ, τ ), for random σ ← $

, Ŝ 0 ν , τ ← $ Ŝ 0 , is ≤ (ν + a − 1)/| Ŝ 0 |. On the other hand, by the soundness of Π sum the probability that the verifier accepts a tuple ((ỹ(σ), Jf K); f ) ∈ / R sum , with f = ũ(X)E(X, σ, τ ) of individual degree 2, is ≤ 2(ℓ + ν)/| Ŝ 0 |. ⊔ ⊓

C

Auxiliary Material on PIOP for Range Checks

C.1

Proof of Lemma 4

Proof. Let us index T B by tuples (idy 1 , . . . , idy N ) ∈ [0, B − 1] N such that

N

T B [idy 1 , . . . , idy N ] =

k=1

(β)

idy k · Y k−1 ∈ R q .

Let dig j (idy) be the function that on input an integer idy, returns the j-th digit P of its base-β decomposition, i.e., idy j such that idy = j idy j β j−1 . Then we can express each element of T B in terms of elements of t β as follows.

N

idy k · Y k−1 =

T B [idy 1 , . . . , idy N ] =

k=1

## N X c

(β)

## N X c

(β)

dig j (idy k ) · β j−1 · Y k−1

k=1 j=1

t β [dig j (idy k )] · Y k−1 · β j−1 .

=

k=1 j=1

<!-- page 45 -->

The above equation implies that ṽ(i) ∈ T B holds ∀i ∈ {0, 1} ℓ if and only if (≤1) ∃µ̃ ∈ Z q [X 1 , . . . , X ℓ , Z 1 , . . . , Z ν , Z 1 ′ , . . . , Z γ ′ ] such that, for ũ = unpack(ṽ),

∀i ∈ {0, 1} ℓ , k ∈ {0, 1} ν : ũ(i, k) =

µ̃(i, k, j) · β to - int(j) ,

j∈{0,1} γ

∀i ∈ {0, 1} ℓ , j ∈ {0, 1} γ , k ∈ {0, 1} ν : ũ(i, k, j) ∈ t β .

(β)

Concretely, µ̃ is determined by the values µ̃(i, k, j) = dig j (ṽ(i)[k]), ∀i ∈ {0, 1} ℓ , j ∈ {0, 1} γ , k ∈ {0, 1} ν . This completes the proof by definition of unpack and the equations (4), (5). ⊔ ⊓

C.2

Proof of Theorem 2

Proof. To prove RBR-soundness, we start by defining a state(T B , JṽK, tr i ) function on every (partial) transcript tr i , from round i = 0 to i = 2 + r range , where r range denotes the number of rounds of the Π̂ range protocol:

- For tr 0 = ∅, state(T B , JṽK, tr 0 ) = 0 iff (T B , JṽK) ∈ / L R range . - For tr 1 = Jµ̃K|(r 1 , . . . , r κ ), state(T B , JṽK, tr 1 ) = 0 iff (t β , Jµ̃K; µ̃) ∈ / R range or ∃i ∈ [κ]: f (r i ) ̸ = 0, where f (X, Z) = ũ(X, Z) − µ̃(X, Z, j) · β to - int(j) .

j∈{0,1} γ

iff - For tr 2 = tr 1 |(µ̃ ∗ 1 , . . . , µ̃ ∗ κ )|s: state(T B , JṽK, tr 2 ) = 0 P (t β , Jµ̃K; µ̃) ∈ / R range or ∃i ∈ [κ] such that ũ(r i ) ̸ = j∈{0,1} γ µ̃ ∗ i (j) · β to - int(j) or µ ∗ i (s) ̸ = µ̃(r i , s). - For tr 2+k = tr 2 |tr ′ k where, for 1 ≤ k ≤ r range , tr ′ k is the partial transcript of Π̂ range at the k-th round: state(T B , JṽK, tr 2+k ) = 0 P iff state ′ (t β , Jµ̃K, tr ′ k ) = 0 or ∃i ∈ [κ] such that ũ(r i ) ̸ = j∈{0,1} γ µ̃ ∗ i (j)·β to - int(j) or µ ∗ i (s) ̸ = µ̃(r i , s).

Let us now show that this state function satisfies the three properties of RBR-soundness. First, it is easy to see that by construction, if (T B , JṽK; ṽ) ∈ / R range then state(T B , JṽK, tr 0 ) = 0. Second, for any complete transcript tr = tr 2+r range = tr 2 |tr ′ r range , by construction we have that if state(T B , JṽK, tr) = 0, then either state ′ (t β , Jµ̃K, tr ′ k ) = 0, which means that the verifier of Π̂ range rejects (by the RBR-soundness of Π̂ range ), or at least one of the verifier’s checks in step 3 fails. Therefore, Π range .V rejects. Third, we show that if state rejects on a partial transcript of round i, for any prover’s message of the round i + 1, we have a concrete (negligible) bound on the probability that state accepts on the next partial transcript. We show this property round by round.

<!-- page 46 -->

Claim. If state(T B , JṽK, tr 0 ) = 0, then for any prover’s message Jµ̃K we have that

Pr

! κ

ℓ + ν

[state(T B , JṽK, tr 1 = (Jµ̃K|(r 1 , . . . , r κ ))) = 1] ≤

r 1 ,...,r κ ← $ Ŝ 0 ℓ+γ

.

| Ŝ 0 |

By definition, state(T B , JṽK, tr 0 ) = 0 iff (T B , JṽK) ∈ / L R range and by Lemma 4 this means that for every µ̃ we have that the polynomial f (X, Z) = ũ(X, Z) − P to - int(j) µ̃(X, Z, j) · β = ̸ or (t , Jµ̃K) ∈ / L . γ β j∈{0,1} R̂ range Instead, state accepting on tr 1 means that (t β , Jµ̃K; µ̃) ∈ R range and ∀i ∈ [κ]: f (r i ) = 0.

Pr[state(T B , JṽK, tr 1 ) = 1 | state(T B , JṽK, tr 0 ) = 0] ^ = Pr[(t β , Jµ̃K; µ̃) ∈ R range f (r i ) = 0 | f (X, Z) ̸ = 0 ∨ (t β , Jµ̃K; µ̃) ∈ / R range ]

i∈[κ]

^

f (r i ) = 0 | f (X, Z) ̸ = 0]

≤ Pr[(

i∈[κ]

Y

=

Pr

[(f (r i ) = 0 | f (X, Z) ̸ = 0 ∧ (t β , Jµ̃K; µ̃) ∈ R range ].

r i ← $ Ŝ 0 ℓ+γ

i∈[κ]

By generalized Schwartz-Zippel, Pr r i ← $ Ŝ 0 [f (r i ) = 0 | f (X, Z) ̸ = 0] ≤ ℓ+γ , | Ŝ 0 | and the claimed bound follows by considering the probability that this occurs for κ independent tests.

Claim. If state(T B , JṽK, tr 1 ) = 0, then for any prover’s message (µ̃ ∗ 1 , . . . , µ̃ ∗ κ ) we have that

γ

Pr γ [state(T B , JṽK, tr 2 = (tr 1 |(µ̃ ∗ 1 , . . . , µ̃ ∗ κ )|s)) = 1] ≤

s← $ Ŝ d

.

| Ŝ d |

By definition, state(T B , JṽK, tr 1 ) = 0 implies that either (t β , Jµ̃K; µ̃) ∈ / R range or ∃i ∈ [κ]: f (r i ) ̸ = 0. On the other P hand, if state(T B , JṽK, tr 2 ) = 1 then (t β , Jµ̃K; µ̃) ∈ R range and ∀i ∈ [κ] ũ(r i ) = j∈{0,1} γ µ̃ ∗ i (j) · β to - int(j) and µ ∗ i (s) = µ̃(r i , s). Consider the specific index i for which f (r i ) ̸ = 0, then we have that

Pr[state(T B , JṽK, tr 2 ) = 1 | state(T B , JṽK, tr 1 ) = 0] κ ^ ≤ Pr[ ũ(r i ) = µ̃ ∗ i (j) · β to - int(j) ∧ µ ∗ i (s) = µ̃(r i , s) | ∃i ∈ [κ] f (r i ) ̸ = 0]

i=1

j∈{0,1} γ

µ̃ ∗ i (j) · β to - int(j) ∧ µ ∗ i (s) = µ̃(r i , s) | f (r i ) ̸ = 0]

≤ Pr[ũ(r i ) =

j∈{0,1} γ

≤ Pr[µ ∗ i (s) = µ̃(r i , s) | ũ(r i ) =

j∈{0,1} γ

= Pr[µ ∗ i (s) = µ̃(r i , s) | µ̃(r i , Z ′ ) ̸ = µ̃ ∗ i (Z ′ )].

µ̃ ∗ i (j) · β to - int(j) ∧ f (r i ) ̸ = 0]

<!-- page 47 -->

P To see the last equality, observe that by definition of f we get that j∈{0,1} γ µ̃(r i , j)· P γ to - int(j) β to - int(j) ̸ = and since β ̸ = 0 and β 2 −1 < q this means γ µ̃ (j) · β

i

j∈{0,1}

that there is a j such that µ ∗ i (j) ̸ = µ̃(r i , j), and thus g(Z ′ ) = µ̃(r i , Z ′ ) − P ˜ ′ , j) ̸ = 0. However, by generalized Schwartz-Zippel, Pr s← $ Ŝ d [g(s) = j∈{0,1} γ µ̃ i (j)· eq(Z 0 | g(Z ) ̸ = 0] ≤ | Ŝ γ | , which proves the claim.

d

Claim. For every k = 0 to r range − 1, if state(T B , JṽK, tr 2+k ) = 0, then for any prover’s message π and every verifier’s random challenge ρ we have that

Pr [state(T B , JṽK, tr 2+k+1 = (tr 2 |tr ′ k |π|ρ) = 1] ≤ δ̂ range .

ρ

For k = 0, if state(T B , JṽK, tr 2 ) = 0 then (t β , Jµ̃K; µ̃) ∈ / R range and, by the RBR-soundness of P Π̂ range , state ′ (t β , Jµ̃K, ∅) = 0. Let E be the event that ∃i ∈ [κ] such that ũ(r i ) ̸ = j∈{0,1} γ µ̃ ∗ i (j) · β to - int(j) or µ ∗ i (s) ̸ = µ̃(r i , s). Then we have

Pr [state(T B , JṽK, tr 2+k+1 ) = 1 | state(T B , JṽK, tr 2+k ) = 0]

ρ

= Pr [state ′ (t β , Jµ̃K, tr ′ k |π|ρ) = 1 ∧ Ē | state ′ (t β , Jµ̃K, tr ′ k ) = 0 ∨ E]

ρ

≤ Pr [state ′ (t β , Jµ̃K, tr ′ k |π|ρ) = 1 | state ′ (t β , Jµ̃K, tr ′ k ) = 0] ≤ δ̂ range .

ρ

⊔ ⊓

where the last bound follows by the RBR-soundness of Π̂ range .

Our Instantiation of the PIOP Π̂ range

D

In this section, we present an instantiation of the PIOP Π̂ range for the relation

R̂ range = {( i , x ; w ) = (t β , Jµ̃K; µ̃) : ∀b ∈ {0, 1} ℓ µ̃(b) ∈ t β },

(≤1)

where the index t β = {0, . . . , β − 1} ⊂ Z and µ̃ ∈ H q [X 1 , . . . , X ℓ ∗ ]. F A building block of our Π̂ range is a PIOP Π̂ range for the oracle relation R̂ range over a finite field F = Z p for an odd prime number p that is sufficiently larger than β, following a bound that we specify below.

Preliminaries. Let us denote X = (X 1 , . . . , X ℓ ∗ ), let q = p 0 · p 1 · · · p L be the product of L+1 distinct prime numbers and let p min denote the smallest of them. Let p be an odd prime number and I p = {−⌊p/2⌋, . . . , ⌊p/2⌋} ⊂ Z. For a positive integer a, let π a : Z → Z a be the canonical quotient map π a (x) = x (mod a). Let π I p be the restriction of π p to I p , which is a bijection, and let ι = π I −1 : Z p → I p be its inverse. p Abusing notation, we extend the definition of these maps to vectors by applying them coordinate-wise and to polynomials by applying them on all their coefficients. For example, given a polynomial f ∈ Z[X 1 , . . . , X n ] we denote by π p (f ) ∈ Z p [X 1 , . . . , X n ] the polynomial obtained by applying π p on all the coefficients of f .

<!-- page 48 -->

We rely on the following proposition, which intuitively formalizes the fact that Z p can emulate computations over signed integers, as long as no overflow occurs.

Proposition 1. Let f ∈ Z[X 1 , . . . , X n ] and x ∈ Z n such that |f (x)| < p/2. Then ι(π p (f )(π p (x))) = f (x).

Proof. Since π p is a ring homomorphism we have π p (f (x)) = π p (f )(π p (x)). Applying ι on both sides ι(π p (f )(π p (x))) = ι(π p (f (x))) = f (x) since f (x) ∈ I p and the restriction of ι ◦ π p to I p acts as the identity function.

Parameters. Let Σ = {0, . . . , σ − 1} ⊆ Z with σ ≤ p min , and notice that π q (Σ) is a subset of the exceptional set Ŝ 0 ⊂ Z q . Let 0 ≤ m ≤ ℓ ∗ be an integer that represents an efficiency tradeoff parameter, and κ ≥ 1 be an integer that represents the number of repetitions. The set of parameters must satisfy the following conditions:

p > 2β · (2σ) m m κ ≈ 2 −λ σ m · 2 ℓ −m = poly(ℓ ∗ )

Intuitively, the first condition ensures correctness of the protocol, the second one ensures soundness, and the third one succinctness.

The Π̂ range protocol. We describe the full protocol in Figure 7.

Theorem 7. Consider the parameters q, p, β, σ, m, κ, ℓ ∗ satisfying equations (23), (24),(25). Let Ŝ d ⊂ H q be an exceptional set. Let t β = {0, . . . , β − 1} ⊂ Z and F be a PIOP for relation R̂ range over the finite field F = Z p that is perlet Π̂ range . Then the Π̂ range protocol fectly complete and has RBR-knowledge error δ range of Figure 7 n is a PIOP for R̂ range with perfect completeness and RBR-knowledge o m κ ℓ ∗ −m ℓ ∗ −m ′ error max ; | Ŝ | + p ; δ range . σ

d

We prove correctness in Section D.1 and RBR-knowledge in Section D.2. When F instantiated with the PIOP Π̂ range from Section D.4, p should additionally be ℓ ∗ > 2 .

Correctness of Π̂ range

D.1

Let µ̃ be a polynomial such that ∀b ∈ {0, 1} ℓ it holds µ̃(b) ∈ t β . By construction, µ̃ ′′ is such that π q (µ̃ ′′ (b)) = µ̃(b), µ̃(b) ∈ t β , and for µ̃ ′ it holds µ̃ ′ (b) ∈ t ′ β ∀b ∈ {0, 1} ℓ since

µ̃ ′ (b) = π p (µ̃ ′′ )(b) = π p (µ̃ ′′ (b)) ∈ π p (t β ) = t ′ β .

<!-- page 49 -->

PIOP Π̂ range for (t β , Jµ̃K; µ̃) ∈ R̂ range

1. P computes µ̃ ′ = π p (µ̃ ′′ ) ∈ Z p [X] where µ̃ ′′ ∈ Z (≤1) [X] is such that, for all b, µ̃ ′′ (b) ∈ t β and π q (µ̃ ′′ (b)) = µ̃(b), and sends Jµ̃ ′ K. V samples r 0 , . . . , r κ−1 ← $ Σ m and sends them to P. 2. P sends (ỹ 0 , ỹ 0 ′ , . . . , ỹ κ−1 , ỹ κ−1 ), where, for η ∈ [κ], r̂ η = π q (r η ), r ′ η = π p (r η ) and:

ỹ η (X m+1 , . . . , X ℓ ∗ ) = µ̃(r̂ η , X m+1 , . . . , X ℓ ∗ ) ∈ H q [X m+1 , . . . , X ℓ ∗ ]

ỹ η ′ (X m+1 , . . . , X ℓ ∗ ) = µ̃ ′ (r ′ η , X m+1 , . . . , X ℓ ∗ ) ∈ Z p [X m+1 , . . . , X ℓ ∗ ]

V samples random points ŝ ← $ Ŝ d ℓ −m and s ′ ← $ Z ℓ p −m . For all η ∈ [κ], V queries Jµ̃K and Jµ̃ ′ K on (r̂ η , ŝ) ∈ H q ℓ and (r ′ η , s ′ ) ∈ Z ℓ p respectively, and checks if

ỹ η (ŝ) = µ̃(r̂ η , ŝ) ∈ H q

and

ỹ η ′ (s ′ ) = µ̃ ′ (r ′ η , s ′ ) ∈ Z p

Then V checks if for all η ∈ [κ], δ ∈ {0, 1} ℓ −m , and l ∈ [0, L]:

ỹ η (δ) mod p l = ι(ỹ η ′ (δ)) mod p l

F 3. P and V run a PIOP Π̂ range for (t ′ β , Jµ̃ ′ K; µ̃ ′ ) ∈ R̂ range , where t ′ β = π p (t β ).

F Figure 7: Construction of the PIOP Π̂ range for R̂ range over H q from Π̂ range for R̂ range over Z p

F accepts. Therefore, by its correctness, the protocol Π̂ range Next, we have to show that the verifier’s checks of step 2 are satisfied. It is straightforward to see that the checks ỹ η (ŝ) = µ̃(r̂ η , ŝ) and ỹ η ′ (s ′ ) = ′ ′ µ̃ (r η , s ′ ) are satisfied by construction. Let us now focus on the last check ỹ η (δ) mod p l = ι(ỹ η ′ (δ)) mod p l . By construction of ỹ η , ỹ η (δ) = µ̃(r̂ η , δ), and since r̂ η = π q (r η ) and π q (µ̃ ′′ ) = µ̃, µ̃(r̂ η , δ) = π q (µ̃ ′′ (r η , δ)). Therefore, ỹ η (δ) mod p l = π q (µ̃ ′′ (r η , δ)) mod p l = µ̃ ′′ (r η , δ) mod p l . To conclude the correctness proof, we need to argue that, for every l, ỹ η (δ) mod p l = µ̃ ′′ (r η , δ) mod p l = ι(ỹ η ′ (δ)) mod p l . The last equality follows by construction of ỹ η ′ – by which ỹ η ′ (δ) = µ̃ ′ (r ′ η , δ) – and by applying Proposition 1 along with the bound on the value of µ̃ ′′ (r η , δ), which we claim below.

Claim. If µ̃ ′′ (b) ∈ t β for all b ∈ {0, 1} ℓ then |µ̃ ′′ (r η , δ)| < 2 m βσ m < p/2.

Proof. By the multi-linearity of the polynomial we have that for all δ ∈ {0, 1} ℓ −m : µ̃ ′′ (r η , δ) = µ̃ ′′ (ϕ, δ)ρ̃ η (ϕ)

ϕ∈{0,1} m

Q m

˜ where ρ̃ η (ϕ) = eq(ϕ; r η ) = i=1 (ϕ i r η,i + (1 − ϕ i )(1 − r η,i )). Given that 0 ≤ r η,i < σ, we have that −σ m < ρ̃ η (ϕ) < σ m ; thus by combining it with the assumption that µ̃ ′′ (ϕ, δ) < β we obtain |µ̃ ′′ (r η , δ)| < 2 m βσ m < p/2.

<!-- page 50 -->

This concludes the correctness proof.

Security of Π̂ range

D.2

We prove the RBR-soundness, from which we get RBR-knowledge by then applying Lemma 6. To prove RBR-soundness, we start by defining a state(t β , Jµ̃K, tr i ) function on every (partial) transcript tr i , from round i = 0 to i = 2 + r range , where r range F denotes the number of rounds of the Π̂ range protocol:

- For tr 0 = ∅, state(t β , Jµ̃K, tr 0 ) = 0 iff (t β , Jµ̃K) ∈ / L R̂ range .

- For tr 1 = Jµ̃ ′ K|(r 0 , . . . , r κ−1 ), state(t β , Jµ̃K, tr 1 ) = 0 iff (t ′ β , Jµ̃ ′ K; µ̃ ′ ) ∈ / R̂ range ℓ ∗ −m or there exist η ∈ [κ], δ ∈ {0, 1} such that f δ (π q (r η )) ̸ = 0 mod q, where f δ (X) ∈ H q [X] is the polynomial

f δ (X) = µ̃(X, δ) − (µ̃ ′′ (X, δ) mod q)

and µ̃ ′′ is the multilinear polynomial such that µ̃ ′′ (b) = ι(µ̃ ′ (b)) for all b ∈ {0, 1} ℓ . - For tr 2 = tr 1 |(ỹ 0 , ỹ 0 ′ , . . . , ỹ κ−1 , ỹ κ−1 )|(ŝ, s ′ ): state(t β , Jµ̃K, tr 2 ) = 0 iff - (t β , Jµ̃ K; µ̃ ) ∈ / R̂ range - or there exist η ∈ [κ], δ ∈ {0, 1} ℓ −m , l ∈ [0, L] such that

ỹ η (δ) mod p l ̸ = ι(ỹ η ′ (δ)) mod p l ,

- or ∃η ∈ [κ] such that ỹ η (ŝ) ̸ = µ̃(r̂ η , ŝ) ∨ ỹ η ′ (s ′ ) ̸ = µ̃ ′ (r ′ η , s ′ ). - For tr 2+k = tr 2 |tr ′ k where, for 1 ≤ k ≤ r range , tr ′ k is the partial transcript of F Π̂ range at the k-th round: state(t β , Jµ̃K, tr 2+k ) = 0 iff - state ′ (t ′ β , Jµ̃ ′ K, tr ′ k ) = 0 - or there exist η ∈ [κ], δ ∈ {0, 1} ℓ −m , l ∈ [0, L] such that

ỹ η (δ) mod p l ̸ = ι(ỹ η ′ (δ)) mod p l ,

- or ∃η ∈ [κ] such that ỹ η (ŝ) ̸ = µ̃(r̂ η , ŝ) ∨ ỹ η ′ (s ′ ) ̸ = µ̃ ′ (r ′ η , s ′ ).

Let us now show that this state function satisfies the three properties of RBR-soundness. First, it is easy to see that by construction, if (t β , Jµ̃K; µ̃) ∈ / R̂ range then state(t β , Jµ̃K, tr 0 ) = 0. Second, for any complete transcript tr = tr 2+r range = tr 2 |tr ′ r range , by construction we have that if state(t β , Jµ̃K, tr) = 0, then either state ′ (t ′ β , Jµ̃ ′ K, tr ′ r range ) = F 0, which means that the verifier of Π̂ range rejects (by the RBR-soundness of F Π̂ range ), or at least one of the verifier’s checks fails. In any of these cases, Π̂ range .V rejects. Third, we show that if state rejects on a partial transcript of round i, for any prover’s message of the round i + 1, we have a concrete (negligible) bound on the probability that state accepts on the next partial transcript. We show this property round by round.

<!-- page 51 -->

Claim. If state(t β , Jµ̃K, tr 0 ) = 0, then for any prover’s message Jµ̃ ′ K we have that m κ Pr . [state(t , Jµ̃K, tr = (Jµ̃ K|(r , . . . , r ))) = 1] ≤ β κ−1 r 0 ,...,r κ−1 ← $ Σ m σ

Proof. By definition, state(t β , Jµ̃K, tr 0 ) = 0 iff (t β , Jµ̃K) ∈ / L R̂ range , that is there

exist δ ∗ ∈ {0, 1} ℓ −m , ϕ ∗ ∈ {0, 1} m such that µ̃(ϕ ∗ , δ ∗ ) ∈ / t β . On the other hand, state accepting on tr 1 means that: (i) (t ′ β , Jµ̃ ′ K; µ̃ ′ ) ∈ R̂ range , i.e., for all δ ∈ {0, 1} ℓ −m , ϕ ∈ {0, 1} m , µ̃ ′ (ϕ, δ) ∈ t ′ β ; (ii) for all η ∈ [κ], δ ∈ {0, 1} ℓ −m : f δ (π q (r η )) = 0 mod q. From (i) and the definition of µ̃ ′′ , we have µ̃ ′′ (ϕ, δ) = ι(µ̃ ′ (π p (ϕ, δ))) ∈ ι(t ′ β ). Since t ′ β = π p (t β ), β < p/2 (from equation (23)), and using ι’s definition, we have ι(π p (t β )) = t β , and thus µ̃ ′′ (ϕ, δ) ∈ t β and the polynomial f δ ∗ (X) is nonzero. Therefore,

Pr[state(t β , Jµ̃K, tr 1 ) = 1 | state(t β , Jµ̃K, tr 0 ) = 0] ^ = Pr[(t ′ β , Jµ̃ ′ K; µ̃ ′ ) ∈ R̂ range f δ (π q (r η )) = 0 | (t β , Jµ̃K; µ̃) ∈ / R̂ range ]

η∈[κ] δ∈{0,1} ℓ −m

^

f δ (π q (r η )) = 0 | (t ′ β , Jµ̃ ′ K; µ̃ ′ ) ∈ R̂ range ∧ (t β , Jµ̃K; µ̃) ∈ / R̂ range ]

≤ Pr[

η∈[κ] δ∈{0,1} ℓ −m

^

f δ ∗ (π q (r η )) = 0 | ∃δ ∗ ∈ {0, 1} ℓ −m : f δ ∗ (X) ̸ = 0]

≤ Pr[

η∈[κ]

Y

=

Pr

[f δ ∗ (π q (r η )) = 0 | f δ ∗ (X) ̸ = 0].

r η ← $ Σ m

η∈[κ]

By generalized Schwartz-Zippel 1, Pr r η ← $ Σ m [f δ ∗ (π q (r η )) = 0 | f δ ∗ (X) ̸ = 0] ≤ m σ , and the claimed bound follows by considering the probability that this occurs for κ independent samples; by equation (24) this bound is ≈ 2 −λ . ⊓ ⊔

Claim. If state(t β , Jµ̃K, tr 1 ) = 0, then for any prover’s message (ỹ 0 , ỹ 0 ′ , . . . , ỹ κ−1 , ỹ κ−1 ) we have that

ℓ ∗ − m . p

ℓ ∗ − m

Pr ′ [state(t β , Jµ̃K, tr 2 = (ỹ 0 , ỹ 0 ′ , . . . , ỹ κ−1 , ỹ κ−1 )|ŝ, s ′ )) = 1] ≤

ŝ,s

+

| Ŝ d |

Proof. The event state(t β , Jµ̃K, tr 2 ) = 1 is the intersection of the following events: ^ ^ (t ′ β , Jµ̃ ′ K; µ̃ ′ ) ∈ R̂ range V 3,η V 4,η,δ,l

η∈[κ]

where

η∈[κ],l∈[0,L] δ∈{0,1} ℓ −m

V 3,η := (ỹ η (ŝ) = µ̃(r̂ η , ŝ)) ∧ (ỹ η ′ (s ′ ) = µ̃ ′ (r ′ η , s ′ ))

V 4,η,δ,l := (ỹ η (δ) mod p l = ι(ỹ η ′ (δ)) mod p l )

<!-- page 52 -->

V Let E 2 be the event “ η∈[κ] (ỹ η (X m+1 , . . . , X ℓ ∗ ) = µ̃(r̂ η , X m+1 , . . . , X ℓ ∗ )) ∧ (ỹ η ′ (X m+1 , . . . , X ℓ ∗ ) = µ̃ ′ (r ′ η , X m+1 , . . . , X ℓ ∗ ))”. By partitioning over E 2 , we upper bound Pr[state(t β , Jµ̃K, tr 2 ) = 1 | state(t β , Jµ̃K, tr 1 ) = 0] by the sum Pr[state(t β , Jµ̃K, tr 2 ) = 1 | E 2 , state(t β , Jµ̃K, tr 1 ) = 0] + Pr[state(t β , Jµ̃K, tr 2 ) = 1 | Ē 2 , state(t β , Jµ̃K, tr 1 ) = 0] The second term can be upper bounded as follows (where we use X to compactly denote X m+1 , . . . , X ℓ ∗ ):

Pr[state(t β , Jµ̃K, tr 2 ) = 1 | Ē 2 , state(t β , Jµ̃K, tr 1 ) = 0] ^ ≤ Pr[ V 3,η | ∃η̄ : ỹ η̄ (X) ̸ = µ̃(r̂ η̄ , X) ∨ ỹ η̄ ′ (X) ̸ = µ̃ ′ (r η̄ ′ , X)]

η∈[κ]

≤ Pr[ỹ η̄ (ŝ) = µ̃(r̂ η̄ , ŝ) ∧ ỹ η̄ ′ (s ′ ) = µ̃ ′ (r η̄ ′ , s ′ ) | ∃η̄ : ỹ η̄ (X) ̸ = µ̃(r̂ η̄ , X) ∨ ỹ η̄ ′ (X) ̸ = µ̃ ′ (r ′ η̄ , X)]

≤ Pr[ỹ η̄ (ŝ) = µ̃(r̂ η̄ , ŝ) | ỹ η̄ (X) ̸ = µ̃(r̂ η̄ , X)] + Pr[ỹ η̄ ′ (s ′ ) = µ̃ ′ (r ′ η̄ , s ′ ) | ỹ η̄ ′ (X) ̸ = µ̃ ′ (r η̄ ′ , X)] ℓ ∗ − m ℓ ∗ − m + ≤ p | Ŝ d |

where the latter inequality follows by applying Schwartz-Zippel over H q (resp. Z p ) with the random ŝ ← $ Ŝ d (resp. s ′ ← $ Z p ). For the first term, we argue that Pr[state(t β , Jµ̃K, tr 2 ) = 1 | E 2 , state(t β , Jµ̃K, tr 1 ) = 0] = 0 as follows.

Pr[state(t β , Jµ̃K, tr 2 ) = 1 | E 2 , state(t β , Jµ̃K, tr 1 ) = 0]   (t ′ β , Jµ̃ ′ K; µ̃ ′ ) ∈ R̂ range V ≤ Pr  η∈[κ],l∈[0,L] V 4,η,δ,l E 2 ∧ ((t ′ β , Jµ̃ ′ K; µ̃ ′ ) ∈ / R̂ range ∨ ∃η̄, ¯ l, δ̄ : f δ̄ (r̂ η̄ ) ̸ = 0 mod p l̄ ) 

δ∈{0,1} ℓ −m



  ≤ Pr  



  V 4,η,δ,l E 2 ∧ (t ′ β , Jµ̃ ′ K; µ̃ ′ ) ∈ R̂ range ∧ ∃η̄, ¯ l, δ̄ : f δ̄ (r̂ η̄ ) ̸ = 0 mod p l̄ )  

^

η∈[κ],l∈[0,L] δ∈{0,1} ℓ −m

≤ Pr µ̃(r̂ η̄ , δ̄) mod p l̄ = ι(µ̃ ′ (r η̄ ′ , δ̄)) mod p l̄

≤ Pr µ̃(r̂ η̄ , δ̄) mod p l̄ = µ̃ ′′ (r η̄ , δ̄) mod p l̄

(t ′ β , Jµ̃ ′ K; µ̃ ′ ) ∈ R̂ range ∧ ∃η̄, ¯ l, δ̄ : f δ̄ (r η̄ ) ̸ = 0 mod p l̄ (t ′ β , Jµ̃ ′ K; µ̃ ′ ) ∈ R̂ range ∧ =0 ∃η̄, ¯ l, δ̄ : f δ̄ (r η̄ ) ̸ = 0 mod p l̄

where the third inequality follows by applying E 2 to the values in the event V 4,η,δ,l and then considering only the event for the tuple η̄, ¯ l, δ̄ for which f δ̄ (r̂ η̄ ) ̸ = 0 mod p l̄ ); the fourth inequality follows by applying Proposition 1 and that |µ̃ ′′ (r η̄ , δ̄)| < p/2 (which is implied by the fact that r η ∈ Σ and 0 ≤ µ̃ ′′ (b) < β). Finally, the last probability is 0, since we are conditioning on f δ̄ (r η̄ ) ̸ = 0 mod p l̄ ). ⊔ ⊓

To prove the last case, recall that, once tr 2 is fixed, so is the event

E := ∃ η ∈ [κ], δ ∈ {0, 1} ℓ −m , l ∈ [0, L] : ¬V 3,η ∨ ¬V 4,η,δ,l ,

<!-- page 53 -->

that is, the event that at least one of the verifier’s checks of step 2 fails. We also let tr ′ 0 = ∅.

Claim. For every k = 0, . . . , r range − 1, if state(t β , Jµ̃K, tr 2+k ) = 0, then for any F prover’s message π of the (k + 1)-th round of Π̂ range we have that

Pr [state(t β , Jµ̃K, tr 2+k+1 ) = 1] ≤ δ range ,

ρ

where tr 2+k+1 = tr 2 |tr ′ k |π|ρ,

F and where the probability is over the (k + 1)-th verifier’s challenge ρ of Π̂ range .

Proof. Since k + 1 ≥ 1, the definition of state on tr 2+k+1 gives

state(t β , Jµ̃K, tr 2+k+1 ) = 1 ⇐⇒ state ′ (t ′ β , Jµ̃ ′ K, tr ′ k |π|ρ) = 1 ∧ Ē.

Moreover, E is determined by tr 2 , hence it is fixed and independent of ρ. We distinguish two cases. If E occurs, then state(t β , Jµ̃K, tr 2+k+1 ) = 1 never occurs and the probability of the claim is 0. If E does not occur, then the event state(t β , Jµ̃K, tr 2+k ) = 0 of the precondition implies state ′ (t ′ β , Jµ̃ ′ K, tr ′ k ) = 0: for k ≥ 1 this is immediate from the definition of state on tr 2+k , whereas for k = 0 the definition of state on tr 2 gives / L R̂ range , which in turn implies state ′ (t ′ β , Jµ̃ ′ K, tr ′ 0 ) = 0 by the first (t ′ β , Jµ̃ ′ K) ∈

F . Therefore, for all property of RBR-soundness (Definition 6) applied to Π̂ range 0 ≤ k < r range ,

Pr [state(t β , Jµ̃K, tr 2+k+1 ) = 1]

ρ

= Pr [state ′ (t ′ β , Jµ̃ ′ K, tr ′ k |π|ρ) = 1 ∧ Ē]

ρ

≤ Pr [state ′ (t ′ β , Jµ̃ ′ K, tr ′ k |π|ρ) = 1] ≤ δ range ,

ρ

where the last inequality follows by the third property of RBR-soundness applied F and to the partial transcript tr ′ k , on which state ′ evaluates to 0. ⊔ ⊓ to Π̂ range

The final n RBR-soundness error is the o max of the three per-round bounds, κ ℓ ∗ −m ℓ ∗ −m ′ namely max m ; | Ŝ | + p ; δ range , where the first term is ≈ 2 −λ by σ d equation (24).

Efficiency of Π̂ range

D.3

F In addition to the cost of running the PIOP Π̂ range , the efficiency of this protocol is as follows.

- The prover sends 1 oracle, Jµ̃ ′ K, whose size is 2 ℓ elements of Z p ; in addition the prover sends κ2 ℓ −m elements of Z q and as many elements of Z p . - The proving time is O(κ · 2 ℓ ), which covers the computation of the partial evaluations of µ̃ and µ̃ sent in round 2.

<!-- page 54 -->

- The verifier time is O(κ · 2 ℓ −m ). - The number of verifier’s queries is 2κ, which includes κ queries to Jµ̃K and κ queries to Jµ̃ ′ K.

Instantiating the concrete parameters. If we target the use of a prime p of 200 bits, and assume ℓ = 20 and β = 2 20 , then we can take for example m = ℓ − ⌈log ℓ⌉ = 15, σ = 2 11 , κ = 18. This gives µ̃ ′′ (r η , δ) < 2 m · β · σ m < p/2 ≈ 2 199 . Looking specifically at the parameters that fit our use of range proofs for the largest circuit in our experiments, then we have: ℓ = 9, β = 2 11 , γ = 2. To fit a 200-bits prime p, then we can set the parameters of the PIOP as m = ℓ, σ = 2 19 , κ = 8. These choices satisfy the correctness and soundness bounds since

µ̃ ′′ (r η , δ) < 2 m · β · σ m = 2 191 < p/2 ≈ 2 199 m κ 9 8 = ≤ 2 −120 σ 2 19 and m = ℓ clearly ensures the succinctness bound.

D.4

## A PIOP for Range Checks over a Finite Field

The protocol relies on the following lemma from [CCC + 25], which simplifies Spartan’s memory checking technique [Set20] to the case of lookups in t β .

Lemma 7 ([CCC + 25]). Let p, ℓ ∗ be positive integers such that p > 2 ℓ . Let F be a field of characteristic p, let µ̃ be an ℓ ∗ -variate multilinear polynomial over F, and let t̃ β be the MLE of a table of size β = 2 b whose elements are all distinct. Then we have that ∀i ∈ {0, 1} ℓ µ̃(i) ∈ { t̃ β (j) : j ∈ {0, 1} b } if and only if there exist polynomials read_ts ∈ F[X 1 , . . . , X ℓ ∗ ], final_cts ∈ F[X 1 , . . . , X b ∗ ] such that WS = RS ∪ S where

WS = {( t̃ β (j), 0) : j ∈ {0, 1} b } ∪ {(µ̃(i), read_ts(i) + 1) : i ∈ {0, 1} ℓ }

RS = {(µ̃(i), read_ts(i)) : i ∈ {0, 1} ℓ }

S = {( t̃ β (j), final_cts(j)) : j ∈ {0, 1} b }.

Following the lemma, the PIOP prover builds the multilinear polynomials read_ts, final_cts and aims to convince the verifier that WS = RS ∪ S. To prove this multiset equality, the verifier sends random challenges σ, τ ← $ F, the prover computes WS t , WS h , RS, S as follows

WS t

z Y

}| { z Y ( t̃ β (j) − τ )

WS =

i∈{0,1} ℓ ∗

j∈{0,1} b ∗

Y

RS =

WS µ

}| { (µ̃(i) + σ(read_ts(i) + 1) − τ )

(µ̃(i) + σ · read_ts(i) − τ )

i∈{0,1} ℓ ∗

Y

S =

( t̃ β (j) + σ · final_cts(j) − τ ),

j∈{0,1} b ∗

<!-- page 55 -->

## F PIOP Π̂ range for (t β , Jµ̃K; µ̃) ∈ R̂ range

1. Let µ̃ ∈ F (≤1) [X 1 , . . . , X ℓ ∗ ]. P constructs read_ts ∈ F (≤1) [X 1 , . . . , X ℓ ∗ ], final_cts ∈ F (≤1) [X 1 , . . . , X b ∗ ] following Lemma 7 applied to µ̃ and t̃ β . Send Jread_tsK, Jfinal_ctsK. V replies with random σ, τ ← $ F. 2. P constructs multilinear polynomials f WS µ , f RS , f WS t , f S such that

(i )

(i )

for α = WS µ , RS: f α (i) = f α 1 (i ′ , 0) · f α 1 (i ′ , 1) ∀i ∈ {0, 1} ℓ (j ) (j ) for α = WS t , S: f α (j) = f α 1 (j ′ , 0) · f α 1 (j ′ , 1) ∀j ∈ {0, 1} b where for a given i ∈ {0, 1} m , i ′ denotes (i 2 , . . . , i m ), and the polynomials f α are

f WS µ = µ̃ + σ · (read_ts + 1) − τ,

f WS t = t̃ β − τ ,

P sends Jf WS µ K, Jf RS K, Jf WS t K, Jf S K.

f RS = µ̃ + σ · read_ts − τ ,

= t̃ β + σ · final_cts − τ

f S

V replies with random χ ← $ F, ρ ← $ F ℓ , ξ ← $ F b . 3. P and V run Π sum for ((0, Jµ ∗ K); µ ∗ ) ∈ R sum and ((0, Jt ∗ K); t ∗ ) ∈ R sum where Jµ ∗ K, Jt ∗ K are of g the virtual oracles: // see Figure 9 for the definition

Jt ∗ K = g χ,ξ J t̃ β K − τ, J t̃ β K + σ · Jfinal_ctsK − τ, Jf WS t K, Jf S K

Jµ ∗ K = g χ,ρ Jµ̃K + σ · (Jread_tsK + 1) − τ, Jµ̃K + σ · Jread_tsK − τ, Jf WS µ K, Jf RS K .

V queries Jf WS µ K, Jf RS K on (1, 0) ∈ F ℓ , Jf WS t K, Jf S K on (1, 0) ∈ F b , and then

checks if f WS t (1, 0) · f WS µ (1, 0) = f RS (1, 0) · f S (1, 0).

b ∗

F , where t β ∈ F 2 , µ̃ ∈ F (≤1) [X 1 , . . . , X ℓ ∗ ]. Figure 8: PIOP Π̂ range

Function g χ,ρ (f 1 , f 2 , f 1 , f 2 )

for k = 1, 2, let f k (X 0 , X) ← (1 − X 0 ) · f k (X) + X 0 · f k (X) Return (f 1 (1, X)−f 1 (X, 0)·f 1 (X, 1)+χ·(f 2 (1, X)−f 2 (X, 0)·f 2 (X, 1)))· eq(ρ, ˜ X)

## F Figure 9: Function g used by PIOP Π̂ range

and the verifier checks that WS t · WS µ = RS · S. The prover must finally convince the verifier that each of the four values is computed correctly; this is done using Quark’s grand product.

Q Lemma 8 (Grand product Lemma [SL20]). P = i∈{0,1} ℓ v(i) if and only if there exists a multilinear polynomial f in ℓ + 1 variables such that f (1, . . . , 1, 0) = P , and ∀i ∈ {0, 1} ℓ it holds f (0, i) = v(i) and f (1, i) = f (i, 0) · f (i, 1).

F In Fig. 8 we present the full specification of the PIOP Π̂ range for R̂ range .

<!-- page 56 -->

F Below, we state and prove the security of Π̂ range . Our proof is inspired to + that of [CCC 25, Lemma 3.2]; here we specialize it to an instantiation over a finite field and prove round-by-round soundness rather than soundness.

Theorem 8. Let p be a prime number and let us consider the finite field F = Z p . F Let ℓ ∗ , β be positive integers such that β = 2 b < p and 2 ℓ < p. Then Π̂ range is a PIOP for R̂ range , with table t β = {0, . . . , β − 1}, that has perfect completeness

ℓ ∗

+2 b p

and RBR-knowledge error δ range = 2

.

b ∗

ℓ ∗

F Proof. We show that Π̂ range is RBR-sound with error δ range = 2 +2 . RBR- p knowledge with the same error follows by applying Lemma 6, using the fact that R̂ range ’s witness is only the polynomial µ̃ that is provided as an oracle in the statement.

Notation. Given the polynomials µ̃, t̃ β , read_ts, final_cts available after the first round, let WS, RS, S be the multisets of pairs as in the statement of Lemma 7, and let WS t , WS µ be the following partition of WS:

WS t = {( t̃ β (j), 0) : j ∈ {0, 1} b }

WS µ = {(µ̃(i), read_ts(i)+1) : i ∈ {0, 1} ℓ }

For α ∈ {WS t , WS µ , RS, S} let use define the polynomials Y P α (Z, Z ′ ) = (a 0 + a 1 · Z − Z ′ ) ∈ F[Z, Z ′ ],

(a 0 ,a 1 )∈α

and let

P (Z, Z ′ ) = P WS t (Z, Z ′ ) · P WS µ (Z, Z ′ ) − P RS (Z, Z ′ ) · P S (Z, Z ′ ).

Note that deg P ≤ 2 ℓ + 2 b and that the coefficients of P are determined by t̃ β , µ̃, read_ts, final_cts, hence they are fixed before V sends σ, τ . For α ∈ {WS t , WS µ , RS, S} let f α (X 0 , X) = (1 − X 0 ) · f α (X) + X 0 · f α (X), where f α is as in Figure 8 and f α is the polynomial sent by P as an oracle in round 2. Let ᾱ = f α (1, 0) = f α (1, . . . , 1, 0) denote the values that V queries in step 6. We define two events, both determined by the oracles available after round 2:

- GP: for every α and every i in the corresponding hypercube ({0, 1} ℓ for α = WS µ , RS and {0, 1} b for α = WS t , S) it holds f α (1, i) = f α (i, 0)·f α (i, 1), i.e., the grand-product statement is satisfied; - V 6 : the check of step 6 passes, i.e., WS t · WS µ = RS · S.

Finally, let state sum be the state function defined by the RBR-soundness of Π sum , and let us define state ′ sum as the state function for the parallel execution of the two sumchecks Π sum in step 3, which is defined to output 0 on a partial transcript of the parallel execution iff state sum outputs 0 on at least one of its two instances.

<!-- page 57 -->

˜ Since f α (X, 0)·f α (X, 1) has degree 2 in each variable and eq(ρ, X) has degree 1, the virtual oracles µ ∗ , t ∗ have degree 3 in each variable. We use that Π sum , run over F on a virtual oracle of degree d in each variable, is RBR-sound with per-round error d/|F|; this is the round-by-round analogue of Theorem 5 and follows from the standard round-by-round analysis of the sum-check protocol [CCH + 19]. Hence the per-round RBR-soundness error of the two instances of Π sum run in step 3 is 3/p. Let us write r sum = max(ℓ ∗ , b ∗ ) for the number of rounds of these Π sum executions in step 3, so that r range = r sum + 2.

The state function. We define state(t β , Jµ̃K, tr i ) on every (partial) transcript, from i = 0 to i = 2 + r sum , as follows:

- For tr 0 = ∅: state(t β , Jµ̃K, tr 0 ) = 0 iff (t β , Jµ̃K) ∈ / L R̂ range . - For tr 1 = Jread_tsK|Jfinal_ctsK|(σ, τ ): state(t β , Jµ̃K, tr 1 ) = 0 iff P (σ, τ ) ̸ = 0.

- For tr 2 = tr 1 | Jf WS µ K, Jf RS K, Jf WS t K, Jf S K |(χ, ρ, ξ): state(t β , Jµ̃K, tr 2 ) = 0

iff ¬V 6 , or ((0, Jµ ∗ K); µ ∗ ) ∈ / R sum , or ((0, Jt ∗ K); t ∗ ) ∈ / R sum . ′′ - For tr 2+k = tr 2 |tr k , where tr ′′ k is the partial transcript of Π sum parallel execution at the k-th round, 1 ≤ k ≤ r sum : state(t β , Jµ̃K, tr 2+k ) = 0 iff ¬V 6 or state ′ sum (0, (Jµ ∗ K, Jt ∗ K), tr ′′ k ) = 0.

We also let tr ′′ 0 = ∅. Note that V 6 is determined by tr 2 , so it is fixed in all the rounds of step 5.

The first property of RBR-soundness holds by construction: if (t β , Jµ̃K) ∈ / L R̂ range then state(t β , Jµ̃K, tr 0 ) = 0. For the second property, let tr = tr 2+r sum be a complete transcript with state(t β , Jµ̃K, tr) = 0. Then either ¬V 6 , in which case the check of step 6 fails, or state sum (tr ′′ r sum ) = 0, in which case the verifier of Π sum rejects by the second F property of RBR-soundness applied to Π sum . In both cases Π̂ range .V rejects. For the third property, we show below that if state rejects on a partial transcript of round i, for any prover’s message of round i + 1, there is a negligible probability that state turns into accept on the next partial transcript, over the random choice of the round-(i + 1) verifier’s challenges.

Claim. If state(t β , Jµ̃K, tr 0 ) = 0, then for any prover’s message Jread_tsK, Jfinal_ctsK,

2 ℓ + 2 b . p

Pr [state(t β , Jµ̃K, tr 1 ) = 1] ≤

σ,τ ← $ F

Proof. By definition state(t β , Jµ̃K, tr 0 ) = 0 there exists i ∗ ∈ {0, 1} ℓ such that µ̃(i ∗ ) ∈ / t β . Since β = 2 b < p, the elements of t β = {0, . . . , β − 1} are pairwise distinct in F, and since 2 ℓ < p we can apply Lemma 7 to µ̃ and t̃ β . This gives us that WS ̸ = RS ∪ S as multisets, for every choice of the polynomials read_ts, final_cts sent by P in round 1. By [Set20, Lemmas 7.2–7.4], we have that the polynomial P (Z, Z ′ ) ̸ = 0 ∈ F[Z, Z ′ ]. Since state(t β , Jµ̃K, tr 1 ) = 1 iff P (σ, τ ) = 0, the claim follows by applying the ⊔ ⊓ Schwartz-Zippell lemma to P , which is of total degree at most 2 ℓ + 2 b .

<!-- page 58 -->

Next we analyze the transition from tr 1 to tr 2 .

Claim. If state(t β , Jµ̃K, tr 1 ) = 0, then for any prover’s message Jf WS µ K, Jf RS K, Jf WS t K, Jf S K,

max(ℓ ∗ , b ∗ ) + 1 . p

Pr [state(t β , Jµ̃K, tr 2 ) = 1] ≤

χ,ρ,ξ

Proof. Recall that state(t β , Jµ̃K, tr 1 ) = 0 means P (σ, τ ) ̸ = 0, and that whether GP occurs is determined only by the prover’s message, independently of χ, ρ, ξ. We distinguish the two cases. If GP occurs, then for every α the polynomial f α satisfies the assumption of Lemma 8 (with polynomial v = f α ). Indeed, f α (0, X) = f α (X) by construc- Q (0) tion and therefore the value ᾱ = f α (1, . . . , 1, 0) = i f α (i). By the definition of Q (0) the polynomials f α we have i f α (i) = P α (σ, τ ). Hence ᾱ = P α (σ, τ ) for all four α, and thus V 6 would give P (σ, τ ) = 0, contradicting state(t β , Jµ̃K, tr 1 ) = 0. Therefore ¬V 6 and state(t β , Jµ̃K, tr 2 ) = 1 with probability 0. If GP does not occur, there are a multiset α ∗ and a point i ∗ of the corresponding hypercube for which the grand-product statement fails. Belowe we analyze the case α ∗ ∈ {WS µ , RS}; the case α ∗ ∈ {WS t , S} is symmetric, following by considering ξ and b ∗ in place of ρ and ℓ ∗ respectively. For i ∈ {0, 1} ℓ let

A(i) = f WS µ (1, i)−f WS µ (i, 0)·f WS µ (i, 1),

B(i) = f RS (1, i)−f RS (i, 0)·f RS (i, 1),

and let G̃ be the multilinear polynomial such that G̃(i) = A(i) + χ · B(i) for all i. P ˜ By the definition of g in Figure 9 and since i∈{0,1} ℓ ∗ h(i) · eq(ρ, i) = h̃(ρ)

for the MLE h̃ of any h : {0, 1} ℓ → F, we have e µ ∗ (i) = G(ρ).

i∈{0,1} ℓ ∗

By the assumption that GP does not occur, there is an i ∗ such that A(i ∗ ) ̸ = 0 or B(i ∗ ) ̸ = 0. Hence, A(i ∗ ) + X · B(i ∗ ) is a non-zero polynomial in X of degree at most 1, and thus A(i ∗ ) + χ · B(i ∗ ) ̸ = 0 except with probability ≤ 1/p e is a non-zero multilinear polynomial in ℓ ∗ variables, over χ ← $ F. Therefore, G e and by Lemma 1 G(ρ) = 0 with probability at most ℓ ∗ /p over ρ ← $ F ℓ . Since state(t β , Jµ̃K, tr 2 ) = 1 implies in particular ((0, Jµ ∗ K); µ ∗ ) ∈ R sum , i.e., e G(ρ) = 0, in this case of α ∗ ∈ {WS µ , RS} we can bound Pr[state(t β , Jµ̃K, tr 2 ) = 1] ≤ (ℓ ∗ + 1)/p. In the symmetric case of α ∗ ∈ {WS t , S} we instead can bound Pr[state(t β , Jµ̃K, tr 2 ) = 1] ≤ (b ∗ + 1)/p. This proves the bound of the claim. ⊔ ⊓

Finally, we analyze the transition from tr 2 to tr 2+k .

Claim. For every k = 0, . . . , r sum − 1, if state(t β , Jµ̃K, tr 2+k ) = 0, then for any prover’s message π of the (k + 1)-th round of step 5,

, p

Pr [state(t β , Jµ̃K, tr 2+k+1 ) = 1] ≤

ρ

<!-- page 59 -->

where tr 2+k+1 = tr 2 |tr ′′ k |π|ρ and the probability is over the (k + 1)-th verifier’s challenge ρ of step 5.

Proof. Since k + 1 ≥ 1, by definition state(t β , Jµ̃K, tr 2+k+1 ) = 1 iff V 6 and state sum (tr ′′ k |π|ρ) = 1. As observed above, V 6 is determined by tr 2 , hence it is fixed and independent of ρ. If V 6 does not occur, then state(t β , Jµ̃K, tr 2+k+1 ) = 1 never occurs and the probability of the claim is 0. If V 6 occurs, then state(t β , Jµ̃K, tr 2+k ) = 0 implies state ′ sum (0, (Jµ ∗ K, Jt ∗ K), tr ′′ k ) = 0. For k ≥ 1 this is immediate from the definition of state on tr 2+k , whereas for k = 0 the definition of state on tr 2 gives that at least one of ((0, Jµ ∗ K); µ ∗ ), ((0, Jt ∗ K); t ∗ ) is not in R sum , which implies state ′ sum (0, (Jµ ∗ K, Jt ∗ K), tr ′′ 0 ) = state ′ sum (0, (Jµ ∗ K, Jt ∗ K), ∅) = 0 by the first property of RBR-soundness applied to the parallel execution of Π sum . The claim then follows by the third property of RBR-soundness applied to the instance of Π sum on which state sum evaluates to 0, whose virtual oracle has degree 3 in each variable. ⊓ ⊔

F The RBR-soundness error of Π̂ range is the maximum of the three per-round bounds established by the claims above, namely ℓ ∗ 2 ℓ + 2 b 2 + 2 b max(ℓ ∗ , b ∗ ) + 1 3 ; ; = . max p p p p

Our Optimized PIOP Π̂ range

D.5

⊔ ⊓

, for the relation R range In this section, we present a PIOP protocol, called Π̂ range of equation (3), which is more optimized than the PIOP Π range obtained by combining the PIOP Π range of Section 4 (Figure 2) with the PIOPs Π̂ range and F described in the previous sections. Π̂ range For this protocol, we reuse the same preliminaries and building blocks of Section D, except that we use the following bound instead of that of equation (24): κ ℓ + ν ≈ 2 −λ σ

We present the protocol in Figure 10. The following theorem states the correctness and security of Π̂ range .

Theorem 9. Let B = 2 b , N = 2 ν , c = 2 γ be such that c | b and β = B 1/c , and let T B and t β = {0, . . . , β − 1} ⊂ Z be the tables of Lemma 4. Consider the parameters q, p, β, σ, m, κ satisfying equations (23), (29) and (25) for ℓ ∗ = F ℓ + ν + γ. Let Π̂ range be a PIOP for the relation R̂ range over the finite field F = Z p that is perfectly complete and has RBR-knowledge error δ range . Then the Π̂ range protocol of Figure 10 is a PIOP for R range with perfect completeness o n κ ℓ+ν+γ−m ′ ; ; δ . and RBR-knowledge error max ℓ+ν range σ p

<!-- page 60 -->

PIOP Π̂ range for (T B , JṽK; ṽ) ∈ R range

(≤1)

1. P computes ũ = unpack(ṽ) ∈ R q [X, Z] and µ̃ ∈ Z (≤1) [X, Z, Z ′ ] as the decomposition of ũ according to equation (4), computes µ̃ ′ = π p (µ̃) ∈ Z p [X, Z, Z ′ ] and sends Jµ̃ ′ K. V samples r 0 , . . . , r κ−1 ← $ Σ ℓ+ν and sends them to P. 2. P sends ( ψ̃ 0 ′ , . . . , ψ̃ κ−1 ), where, for η ∈ [κ], r ′ η = π p (r η,1 , . . . , r η,m ) and:

ψ̃ η ′ (X m+1 , . . . X ℓ , Z, Z ′ ) = µ̃ ′ (r ′ η , X m+1 , . . . X ℓ , Z, Z ′ )

V samples s ′ ← $ F ℓ−m+ν+γ . p For all η ∈ [κ], queries Jµ̃ ′ K on (r ′ η , s ′ ) ∈ F ℓ+ν+γ and the virtual oracle JũK on p r̂ η = π q (r η ) ∈ Z ℓ+ν . Then V checks if: q

∀η ∈ [κ] : ψ̃ η ′ (s ′ ) = µ̃ ′ (r ′ η , s ′ ) ∈ Z p

and ∀l ∈ [0, L], η ∈ [κ] ˜ ũ(r̂ η ) mod p l = ι( ψ̃ η ′ (δ, k)) · eq(δ; (r η,m+1 , . . . , r η,ℓ+ν )) · β to - int(k) mod p l

δ∈{0,1} ℓ+ν−m k∈{0,1} γ

F 3. P and V run a PIOP Π̂ range for (t ′ β , Jµ̃ ′ K; µ̃ ′ ) ∈ R̂ range , where t ′ β = π p (t β ).

F over Z p from Π̂ range Figure 10: Construction of the PIOP Π̂ range

F from Section D.4, p should additionally When instantiated with the PIOP Π̂ range ℓ+ν+γ be > 2 . ≤m >m = Throughout the two proofs below we write r η = (r ≤m η , r η ), where r η ≤m >m (r η,1 , . . . , r η,m ) and r η = (r η,m+1 , . . . , r η,ℓ+ν ), so that r η = π p (r η ) and r̂ η = π q (r η ).

Correctness of Π̂ range . Let ṽ be a polynomial such that ∀b ∈ {0, 1} ℓ it holds ṽ(b) ∈ T B . By Lemma 4, the polynomial µ̃ ∈ Z (≤1) [X, Z, Z ′ ] computed by P in step 1 satisfies equation (4) and µ̃(b) ∈ t β for all b ∈ {0, 1} ℓ+ν+γ . By construction, for µ̃ ′ = π p (µ̃) it holds µ̃ ′ (b) ∈ t ′ β ∀b ∈ {0, 1} ℓ+ν+γ since

µ̃ ′ (b) = π p (µ̃)(b) = π p (µ̃(b)) ∈ π p (t β ) = t ′ β .

F Therefore, by its correctness, the protocol Π̂ range accepts. Next, we have to show that the verifier’s checks of step 2 are satisfied. It is straightforward to see that the checks ψ̃ η ′ (s ′ ) = µ̃ ′ (r ′ η , s ′ ) are satisfied by construction. Let us now focus on the last check. By construction of ψ̃ η ′ we have ψ̃ η ′ (δ, k) = ′ ′ µ̃ (r η , δ, k) and, by applying Proposition 1 to µ̃ on the point (r ≤m η , δ, k) ∈ Z ℓ+ν+γ along with the bound on the value of µ̃(r ≤m , δ, k), which we claim later, η

ι( ψ̃ η ′ (δ, k)) = ι π p (µ̃) π p (r ≤m η , δ, k)

= µ̃(r ≤m η , δ, k).

<!-- page 61 -->

Therefore, by the multilinearity of µ̃, for the right-hand side of the last check we obtain the following equality over the integers: to - int(k) ˜ ι( ψ̃ η ′ (δ, k)) · eq(δ; r >m η ) · β

δ∈{0,1} ℓ+ν−m k∈{0,1} γ

β to - int(k)

µ̃(r η , k) · β to - int(k) .

˜ µ̃(r ≤m r >m η , δ, k) · eq(δ; η )=

=

k∈{0,1} γ

δ∈{0,1} ℓ+ν−m

k∈{0,1} γ

Finally, both sides of equation (4) are multilinear in (X, Z) and agree on {0, 1} ℓ+ν , so that P equation, once reduced modulo q, holds as an identity of polynomials, i.e. to - int(k) π q = ũ(X, Z). Since π q is a ring homomork∈{0,1} γ µ̃(X, Z, k) · β P to - int(k) phism, evaluating on r η gives ũ(r̂ η ) = π q , and k∈{0,1} γ µ̃(r η , k) · β

thus the last check is satisfied for all η ∈ [κ] and l ∈ [0, L].

Claim. If µ̃(b) ∈ t β for all b ∈ {0, 1} ℓ+ν+γ then, for all η ∈ [κ], δ ∈ {0, 1} ℓ+ν−m m m and k ∈ {0, 1} γ , µ̃(r ≤m < p/2. η , δ, k) < 2 βσ

Proof. By the multi-linearity of the polynomial we have that µ̃(r ≤m µ̃(ϕ, δ, k) ρ̃ η (ϕ) η , δ, k) =

ϕ∈{0,1} m

Q m ˜ where ρ̃ η (ϕ) = eq(ϕ; r ≤m η ) = i=1 (ϕ i r η,i + (1 − ϕ i )(1 − r η,i )). Given that 0 ≤ r η,i < σ, we have that −σ m < ρ̃ η (ϕ) < σ m ; thus by combining it with the assumption that µ̃(ϕ, δ, k) ∈ t β , i.e. 0 ≤ µ̃(ϕ, δ, k) ≤ β − 1, we obtain m m ⊔ ⊓ µ̃(r ≤m η , δ, k) < 2 βσ , which is smaller than p/2 by equation (23).

This concludes the correctness proof.

. We prove the RBR-soundness, from which we get RBR- Security of Π̂ range knowledge by then applying Lemma 6. As in Section D.2, let µ̃ ′′ be the multilinear polynomial in Z (≤1) [X, Z, Z ′ ] such that µ̃ ′′ (b) = ι(µ̃ ′ (b)) for all b ∈ {0, 1} ℓ+ν+γ ; note that µ̃ ′′ = µ̃ when P is honest. We define the state(T B , JṽK, tr i ) function on every (partial) transcript tr i , from round i = 0 to i = 2 + r range , where r range denotes the number of rounds F of the Π̂ range protocol:

- For tr 0 = ∅, state(T B , JṽK, tr 0 ) = 0 iff (T B , JṽK) ∈ / L R range . - For tr 1 = Jµ̃ ′ K|(r 0 , . . . , r κ−1 ), state(T B , JṽK, tr 1 ) = 0 iff (t ′ β , Jµ̃ ′ K) ∈ / L R̂ range or there exists η ∈ [κ] such that F (r̂ η ) ̸ = 0, where F (X, Z) ∈ Z q [X, Z] is the multilinear polynomial   F (X, Z) = ũ(X, Z) − π q  µ̃ ′′ (X, Z, k) · β to - int(k)  .

k∈{0,1} γ

<!-- page 62 -->

- For tr 2 = tr 1 |( ψ̃ 0 ′ , . . . , ψ̃ κ−1 )|s ′ : state(T B , JṽK, tr 2 ) = 0 iff - (t β , Jµ̃ K) ∈ / L R̂ range - or there exists η ∈ [κ] such that ¬V 1,η , or there exist η ∈ [κ] and l ∈ [0, L] such that ¬V 2,η,l , where V 1,η := ψ̃ η ′ (s ′ ) = µ̃ ′ (r ′ η , s ′ )



  V 2,η,l :=  ũ(r̂ η ) mod p l = 

δ∈{0,1} k∈{0,1} γ



  to - int(k) ˜ ι( ψ̃ η ′ (δ, k)) · eq(δ; r >m ) · β mod p l  η  ℓ+ν−m

are the two checks of step 2. - For tr 2+k = tr 2 |tr ′ k where, for 1 ≤ k ≤ r range , tr ′ k is the partial transcript of F at the k-th round: state(T B , JṽK, tr 2+k ) = 0 iff state ′ (t ′ β , Jµ̃ ′ K, tr ′ k ) = 0, Π̂ range or there exists η ∈ [κ] such that ¬V 1,η , or there exist η ∈ [κ] and l ∈ [0, L] such that ¬V 2,η,l .

Let us now show that this state function satisfies the three properties of RBR-soundness. First, it is easy to see that by construction, if (T B , JṽK) ∈ / L R range then state(T B , JṽK, tr 0 ) = 0. Second, for any complete transcript tr = tr 2+r range = tr 2 |tr ′ r range , by construction we have that if state(T B , JṽK, tr) = 0, then either state ′ (t ′ β , Jµ̃ ′ K, tr ′ r range ) = 0, F rejects by the second property of RBR- which means that the verifier of Π̂ range F , or at least one of the verifier’s checks soundness (Definition 6) applied to Π̂ range of step 2 fails. In any of these cases, Π̂ range .V rejects. Third, we show that if state rejects on a partial transcript of round i, for any prover’s message of the round i + 1, we have a concrete (negligible) bound on the probability that state accepts on the next partial transcript. We show this property round by round.

Claim. If state(T B , JṽK, tr 0 ) = 0, then for any prover’s message Jµ̃ ′ K we have that κ ℓ + ν Pr [state(T B , JṽK, tr 1 = (Jµ̃ K|(r 0 , . . . , r κ−1 ))) = 1] ≤ . σ r 0 ,...,r κ−1 ← $ Σ ℓ+ν

Proof. By definition, state(T B , JṽK, tr 1 ) = 1 means that: (i) (t ′ β , Jµ̃ ′ K) ∈ L R̂ range , i.e., µ̃ ′ (b) ∈ t ′ β for all b ∈ {0, 1} ℓ+ν+γ ; (ii) for all η ∈ [κ]: F (r̂ η ) = 0. From (i) and the definition of µ̃ ′′ we have µ̃ ′′ (b) = ι(µ̃ ′ (b)) ∈ ι(t ′ β ); since t β = π p (t β ) and β < p/2 (from equation (23)), using ι’s definition we have ι(π p (t β )) = t β , and thus µ̃ ′′ (b) ∈ t β for all b ∈ {0, 1} ℓ+ν+γ . In particular, the (≤1) multilinear polynomial π q (µ̃ ′′ ) ∈ Z q [X, Z, Z ′ ] satisfies equation (5). On the other hand, state(T B , JṽK, tr 0 ) = 0 means (T B , JṽK) ∈ / L R range , and therefore, by

<!-- page 63 -->

Lemma 4, π q (µ̃ ′′ ) must violate equation (4), i.e., there exists i ∗ ∈ {0, 1} ℓ+ν such P ′′ ∗ to - int(k) that ũ(i ∗ ) ̸ = π , i.e. F (i ∗ ) ̸ = 0 and thus the γ µ̃ (i , k) · β

q

k∈{0,1}

polynomial F (X, Z) is nonzero. Notice that F is determined by ṽ and by the oracle Jµ̃ ′ K, hence it is fixed before V samples r 0 , . . . , r κ−1 , and that these are sampled independently of each other. Therefore,

Pr[state(T B , JṽK, tr 1 ) = 1 | state(T B , JṽK, tr 0 ) = 0]   ^ ≤ Pr  F (π q (r η )) = 0 F (X, Z) ̸ = 0 

η∈[κ]

Y

=

Pr

[F (π q (r η )) = 0 | F (X, Z) ̸ = 0] .

r η ← $ Σ ℓ+ν

η∈[κ]

Since F is multilinear in ℓ + ν variables, hence of total degree at most ℓ + ν, and since π q (Σ) is a subset of the exceptional set Ŝ 0 of size σ, by generalized Schwartz-Zippel (Lemma 1) we get Pr r η ← $ Σ ℓ+ν [F (π q (r η )) = 0 | F (X, Z) ̸ = 0] ≤ ℓ+ν σ , and the claimed bound follows by considering the probability that this occurs for κ independent samples; by equation (29) this bound is ≈ 2 −λ . ⊓ ⊔

Claim. If state(T B , JṽK, tr 1 ) = 0, then for any prover’s message ( ψ̃ 0 ′ , . . . , ψ̃ κ−1 ) we have that

ℓ − m + ν + γ . p

Pr ′ [state(T B , JṽK, tr 2 = (tr 1 |( ψ̃ 0 ′ , . . . , ψ̃ κ−1 )|s ′ )) = 1] ≤

s

V Proof. Let E 2 be the event “ η∈[κ] ψ̃ η ′ (X m+1 , . . . , X ℓ , Z, Z ′ ) = µ̃ ′ (r ′ η , X m+1 , . . . , X ℓ , Z, Z ′ ) ”, i.e. the event that the polynomials sent by P are the correct partial evaluations of µ̃ ′ . Notice that E 2 is determined by the prover’s message, hence it is fixed and independent of s ′ ; the same holds for the event (t ′ β , Jµ̃ ′ K) ∈ L R̂ range , which is determined by the oracle sent in step 1. We distinguish the two cases. If E 2 does not occur, let η̄ be an index for which the two polynomials differ. Since state(T B , JṽK, tr 2 ) = 1 requires in particular V 1,η̄ , we have

Pr[state(T B , JṽK, tr 2 ) = 1 | Ē 2 , state(T B , JṽK, tr 1 ) = 0] h i ℓ − m + ν + γ ≤ Pr ψ̃ η̄ ′ (s ′ ) = µ̃ ′ (r ′ η̄ , s ′ ) ψ̃ η̄ ′ ̸ = µ̃ ′ (r η̄ ′ , ·) ≤ , p

where the last inequality follows by the Schwartz-Zippel lemma over Z p , applied to the non-zero multilinear polynomial ψ̃ η̄ ′ − µ̃ ′ (r ′ η̄ , ·) in ℓ − m + ν + γ variables, of total degree at most ℓ − m + ν + γ, with the random s ′ ← $ Z ℓ−m+ν+γ . p If E 2 occurs, we argue that Pr[state(T B , JṽK, tr 2 ) = 1 | E 2 , state(T B , JṽK, tr 1 ) = 0] = 0. We may assume (t ′ β , Jµ̃ ′ K) ∈ L R̂ range , as otherwise state(T B , JṽK, tr 2 ) = 0 by definition. As in the proof of the previous claim, this gives µ̃ ′′ (b) ∈ t β for

<!-- page 64 -->

all b ∈ {0, 1} ℓ+ν+γ , so that the claim of the correctness proof, applied to µ̃ ′′ in place of µ̃, gives µ̃ ′′ (r ≤m η , δ, k) < p/2. Hence, by Proposition 1 and E 2 ,

ι( ψ̃ η ′ (δ, k)) = ι µ̃ ′ (r ′ η , δ, k) = µ̃ ′′ (r ≤m η , δ, k)

∀η ∈ [κ], δ ∈ {0, 1} ℓ+ν−m , k ∈ {0, 1} γ .

By the same computation as in the correctness proof — which only uses the mul- P ′′ ′′ to - int(k) tilinearity of µ̃ — the right-hand side of V 2,η,l equals π q mod k∈{0,1} γ µ̃ (r η , k) · β p l , and therefore   ^ V 2,η,l ⇐⇒ ũ(r̂ η ) = π q  µ̃ ′′ (r η , k) · β to - int(k)  ⇐⇒ F (r̂ η ) = 0,

k∈{0,1} γ

l∈[0,L]

where the first equivalence holds since p 0 · · · p L = q and thus, by the CRT, two elements of Z q are equal if and only if they are equal modulo p l for all l ∈ [0, L]. Since state(T B , JṽK, tr 1 ) = 0 and we assumed (t ′ β , Jµ̃ ′ K) ∈ L R̂ range , there exists η̄ ∈ [κ] with F (r̂ η̄ ) ̸ = 0, hence ¬V 2,η̄,l̄ for some ¯ l ∈ [0, L] and state(T B , JṽK, tr 2 ) = 0. ⊔ ⊓

To prove the last case, recall that, once tr 2 is fixed, so is the event

E := ∃ η ∈ [κ], l ∈ [0, L] : ¬V 1,η ∨ ¬V 2,η,l ,

that is, the event that at least one of the verifier’s checks of step 2 fails. We also let tr ′ 0 = ∅.

Claim. For every k = 0, . . . , r range − 1, if state(T B , JṽK, tr 2+k ) = 0, then for any F we have that prover’s message π of the (k + 1)-th round of Π̂ range

Pr [state(T B , JṽK, tr 2+k+1 ) = 1] ≤ δ range ,

ρ

where tr 2+k+1 = tr 2 |tr ′ k |π|ρ,

F . and where the probability is over the (k + 1)-th verifier’s challenge ρ of Π̂ range

Proof. Since k + 1 ≥ 1, the definition of state on tr 2+k+1 gives

state(T B , JṽK, tr 2+k+1 ) = 1 ⇐⇒ state ′ (t ′ β , Jµ̃ ′ K, tr ′ k |π|ρ) = 1 ∧ Ē.

Moreover, E is determined by tr 2 , hence it is fixed and independent of ρ. We distinguish two cases. If E occurs, then state(T B , JṽK, tr 2+k+1 ) = 1 never occurs and the probability of the claim is 0. If E does not occur, then the event state(T B , JṽK, tr 2+k ) = 0 of the precondition implies state ′ (t ′ β , Jµ̃ ′ K, tr ′ k ) = 0: for k ≥ 1 this is immediate from the definition of state on tr 2+k , whereas for k = 0 the definition of state on tr 2 gives (t ′ β , Jµ̃ ′ K) ∈ / L R̂ range , which in turn implies state ′ (t ′ β , Jµ̃ ′ K, tr ′ 0 ) = 0 by the first

<!-- page 65 -->

F property of RBR-soundness (Definition 6) applied to Π̂ range . Therefore, for all 0 ≤ k < r range ,

Pr [state(T B , JṽK, tr 2+k+1 ) = 1]

ρ

= Pr [state ′ (t ′ β , Jµ̃ ′ K, tr ′ k |π|ρ) = 1 ∧ Ē]

ρ

≤ Pr [state ′ (t ′ β , Jµ̃ ′ K, tr ′ k |π|ρ) = 1] ≤ δ range ,

ρ

where the last inequality follows by the third property of RBR-soundness applied F to Π̂ range and to the partial transcript tr ′ k , on which state ′ evaluates to 0. ⊔ ⊓

The final n RBR-soundness error is the o max of the three per-round bounds, ℓ+ν κ ℓ−m+ν+γ ; δ range , where the first term is ≈ 2 −λ by equanamely max ; σ p tion (29).

Efficiency of Π̂ range In this section, we detail the efficiency of the PIOP F (instantiated with ℓ ∗ = ℓ+ν+γ) Π̂ range when instantiated with the PIOP Π̂ range described in the previous section. The PIOP has the following efficiency profile:

F involves two rounds - the number of rounds is r = max(ℓ ∗ , b/c) + 4, as Π̂ range plus the parallel execution of two sum-checks of size 2 ℓ and 2 b/c , and then itself; there are two rounds in Π̂ range - the prover sends o = 7 oracles that are multilinear polynomials over Z p : 3 of size 2 b/c and 4 of size 2 ℓ ; in addition, the prover sends the polynomials ( ψ̃ 0 , . . . , ψ̃ κ−1 ) that are κ · 2 ℓ −m elements of Z p ; - the proving time is T P = O(κ·2 ℓ +2 b/c ) since this is the time needed to build the 7 oracle polynomials and since the two sum-checks can be run in linear time as they involve a product of multilinear polynomials, plus considering the cost of computing the κ partial evaluations of µ̃ ′ ; - the verifier time is T V = O(ℓ ∗ + b/c + κ · 2 ℓ −m ) since O(ℓ ∗ + b/c) is the verification time of the two sum-check executions and since O(κ · 2 ℓ −m ) is the time to perform the last verification checks in the round 2 of Π̂ range ; we recall that this term is poly(ℓ + ν + γ) by equation (25). Additionally, as we show below V has to compute the evaluation of t̃ ′ β on (r ∗ t , 0), (r ∗ t , 1), which P b/c can be done in time O(b/c) since t̃ ′ β (X 1 , . . . , X b/c ) = k=1 X k · 2 k−1 . - the number of verifier’s queries is q = 15 + 2κ, as justified below.

F Assume that in Π̂ range the sum-check on µ ∗ (resp. t ∗ ) ends with a query of V of the virtual oracle on r µ (resp. r t ). Below, for a vector x we denote x[1, . . . , m] its prefix of length m, and for x = (x 1 , . . . , x m ), we denote by x ∗ the vector (x 2 , . . . , x m ). The protocol requires the following queries to the 7 oracles over Z p :

- Jµ̃ ′ K on (r ′ 0 , s ′ ), . . . , (r ′ κ−1 , s ′ ), (r ∗ µ , 0), (r ∗ µ , 1);

<!-- page 66 -->

- Jread_tsK on (r ∗ µ , 0), (r ∗ µ , 1); - Jfinal_ctsK on (r ∗ t , 0), (r ∗ t , 1); - Jf WS µ K on r µ , (r ∗ µ , 0), (r ∗ µ , 1), (1, 0)

- Jf RS K on r µ , (r ∗ µ , 0), (r ∗ µ , 1), (1, 0) - Jf WS t K on r t , (r ∗ t , 0), (r ∗ t , 1), (1, 0) - Jf S K on r t , (r ∗ t , 0), (r ∗ t , 1), (1, 0)

In addition, in the protocol Π̂ range , the verifier queries Junpack(ṽ)K on r̂ 1 , . . . , r̂ κ , which turn into querying the packed polynomial JṽK on r̂ 1 [1, . . . , ℓ], . . . , r̂ κ [1, . . . , ℓ]. To minimize the number of evaluation proofs, it is possible to apply a simple batching optimization to all those evaluations of the form (r ∗ , 0), (r ∗ , 1). In this case, the prover first sends the results y and y ′ of the evaluations in (r ∗ , 0) and (r ∗ , 1) respectively, the verifier chooses a random point θ, and queries the polynomial on (r ∗ , θ). Then, assuming the result of this query is y ′′ , the verifier checks that y ′′ = (1 − θ)y + θy ′ . By using this optimization, we obtain in total q = 15 + 2κ queries, as mentioned earlier.

Instantiating the concrete parameters. By equations (23) and (29), the parameters must satisfy

log p > 1 + log β + m · (1 + log σ)

λ , log σ − log(ℓ + ν)

κ ≥

and

while the dominant term of the proof size is κ · 2 ℓ+ν+γ−m elements of Z p . Differently from Π̂ range , where the challenges r η are used to fix m ≤ ℓ ∗ variables of µ̃, here they are sampled in Σ ℓ+ν and thus m can be taken as large as ℓ + ν. This is what makes the proof size independent of N : for m ≤ ℓ we would have 2 ℓ+ν+γ−m ≥ 2 ν+γ = c · N , i.e., a proof size linear in N , whereas taking m > ℓ removes this factor. Let us consider the parameters used in the range proofs for the largest circuit in our experiments, that is ℓ = 9, β = 2 11 , γ = 2 and N = 2 13 (hence ν = 13 and ℓ + ν = 22), and let us target λ = 128 and a prime p of 208 bits. Then we can take for example m = 15, σ = 2 11 , κ = 20, which gives κ ℓ + ν m 2β · (2σ) = 2 < p, = ≤ 2 −130 , σ 2 11

and a proof size of κ · 2 ℓ+ν+γ−m = 20 · 2 9 = 10240 elements of Z p , i.e., about 260 KB. This is the choice we use in our experiments (Table 3). Alternatively, by lowering σ we can push m up to its maximum ℓ + ν at the price of more repetitions. Taking m = ℓ + ν = 22, σ = 2 7 , κ = 51, we get κ 51 ℓ + ν 2β · (2σ) m = 2 188 < p, = ≤ 2 −129 , σ 2 7

and a proof size of 51 · 2 2 = 204 elements of Z p , i.e., about 5 KB. The price of this second choice is a larger κ, which affects the prover’s running time, that grows as O(κ · 2 ℓ+ν+γ ), and the batch size of the two evaluation proofs.

<!-- page 67 -->

E

Additional material for Section 5

E.1

The copycon wiring predicate in Equation (7)

Throughout this subsection z denotes the #(copy)-bit index of the copy gate, i.e. the block Z [#(copy)] that Eq. (7) feeds to the predicate. Let s := max(µ, #(in)), so that m ′ = s + 1 and y = (y [s] , Y s ), where the most significant variable Y s = Y m ′ −1 is the one that g uses to choose between Ṽ in and Ṽ 3,quot (see Section 5.1). copycon(t, z, x, y) always evaluates to zero, except in the two following cases when it evaluates to 1:   (Y m ′ −1 = 0) ∧ (x [d,m) = 1) ∧ (y [#(in),s) = 1) ∧ (t = (0, 1))       ∧( Ṽ (x ) multiplies Ṽ (y ) in the (z)-th check) 3,ptxt [d] in [#(in)]   or     (Y m ′ −1 = 1) ∧ (x [d,m) = 1) ∧ (y [µ,s) = 1) ∧ (t = (0, 1))      ∧( Ṽ 3,ptxt (x [d] ) multiplies Ṽ 3,quot (y [µ] ) in the (z)-th check)

copycon(t, ^ z, x, y) can be described as: copycon(T, ^ Z, X, Y) = e f q(T, (0, 1)) · copycon ^ (Z, X, Y), where copycon ^ (Z, X, Y) can be described exactly as in Eq. (30) by removing the condition t = (0, 1). Whenever a party needs to evaluate copycon(T, ^ Z, X, Y) at a specific point, they can do it from the evaluation of copycon ^ (Z, X, Y). In particular, the committed polynomial is copycon ^ , which has #(copy) + m + m ′ variables.

Wiring predicates from [CCC + 25]

E.2

Let us provide the description of the wiring predicates introduced in [CCC + 25].

( 1, if wire x holds the z-th c ′ value. rescon 1 (z, x) = 0, otherwise.    −1, if wire x holds the z-th remainder. rescon 3 (z, x) = −p l , if x belongs to the l-th HE layer and holds the z-th quotient.   0, otherwise. ( 1, if wire x holds the z-th d 2 value. bdcon 2 (z, x) = 0, otherwise.    −PW ω l (1)[i], if x belongs to the l-th HE layer and holds bdcon 3 (z, x) = the i-th decomposition of the z-th d 2 value.   0, otherwise.

<!-- page 68 -->

 evk l,b [i], if wire x belongs to the l-th HE layer and     holds the i-th decomposition of the d 2 value evk(z, x) =  corresponding to the z-th c ′ [b], where b ∈ {0, 1}.    0, otherwise.

The following predicate was used in [CCC + 25] but originates from [LXZ21] ( 1, if V (x) · V (y) is added to V 2 (z). Xmult(z, x, y) = 0, otherwise.

In our work, we have introduced several changes so as to improve efficiency. First of all, we have added the metadata variables T that distinguish among the different kinds of gate. Second, we have drastically reduced the amount of X variables by converting them into Z variables. Notice how, in our case, rescon 1 (z, x) and bdcon 2 (z, x) have simplified practically to the point of disappearance. We elaborate on this next, in Appendix E.3. This conversion is not applied everywhere. The predicates rescon 3 , bdcon 3 and evk above do not merely test z against x: they read the HE layer l of the wire x in order to apply the leveldependent constants p l , PW ω l (1)[i] and evk l,b [i]. The δ variables encoding that layer must therefore stay in X. What our version changes is only that the layer is matched against Z [δ] and used to select the constant by a single fused factor e f q(bin(l), Z [δ] )f eq(bin(l), X [δ] ), keeping the MLE multilinear in both blocks. The evolution of the predicates in [CCC + 25] to the ones we propose is implicit by the definitions above, Appendix E.3 and the detailed description of our MLEs in Section 5.1.

E.3

Too many gates in Equation (7)?

Notice how rescon ^ 1 (T) = e f q(T, (0, 0)) does not include any Z variables and hence ∀z ∈ {0, 1} max(µ,#(copy)) , rescon ^ 1 (0, 0) · Ṽ 1 (z [µ] ) = Ṽ 1 (z [µ] ). This would seem to have the effect of having “too many rescon ^ gates”. There are two different cases to consider here, on which we elaborate next:

- First we have the excess gates that result from the difference between the actual number of rescon ^ gates and the next power of two following that number, i.e. 2 µ (all possible values for z [µ] ). Let us label those exceeding gates as Ê ⊆ {0, 1} µ . Whereas an honest prover would set Ṽ 1 (ẑ) = 0 ∀ẑ ∈ Ê, a malicious prover could choose to put some non-zero values in there. The same discussion applies verbatim to copycon ^ 3,copy (T)· Ṽ 3,copy (Z [#(copy)] ) and to the #(copy) exceeding copy gates in {0, 1} , since copycon ^ 3,copy carries no Z either. Such malicious prover would then have two options: Either these values respect the constraints given in Equations (7), (11) and their dependencies, or they do not. In the latter case, the soundness of sumcheck will detect this and abort. In the former case, this would ultimately do no harm, since ^ predicates from Equation (12) are such that Xmult(ẑ, ^ the Xmult x, y) = 0 ∀(ẑ, x, y) ∈ ( Ê × {0, 1} s × {0, 1} s ). This is by the very definition of Ê.

<!-- page 69 -->

- Second, there are the potentially exceeding max(µ, #(copy)) − µ variables in Z. These extra values mean repeating the same check that many times, which is harmless both in terms of soundness and efficiency. More concretely, ∀z ′ extra ∈ {0, 1} max(µ,#(copy))−µ the “ rescon ^ part” (i.e. T = (0, 0)) of Equations (7) simplifies to

Ṽ 0 (0, 0, z [µ] , z ′ extra ) = Ṽ 1 (z [µ] ) rescon ^ 3 (0, 0, z [δ] , x) · Ṽ 3,rc 3 (x [δ] , z [δ,µ) , x δ ) +

x∈{0,1} m

= Ṽ 1 (z [µ] ) +

b=0

rescon ^ 3 (0, 0, z [δ] , x (b) ) · Ṽ 3,rc 3 (z [µ] , b),

where x (b) := (z [δ] , b, 1). The second equality uses that, for boolean z, the fused factor e f q(bin(l), z [δ] )f eq(bin(l), x [δ] ) inside rescon ^ 3 leaves a single nonzero value of x [δ] , namely x [δ] = z [δ] . Notice how the right hand side is independent of z ′ extra ∈ {0, 1} max(µ,#(copy))−µ .

E.4

Additional material for Section 5.2

Recombining into Equation (12) Here we continue with the explanation of how to regroup values coming from Equation (7) and Equation (11) so as to execute sumcheck on Equation (12). This essentially follows [CCC + 25]. For a set S among {d 01 , d 2 }, define predicates C 2,S (Y, Z) as follows: ( 1, if wire y in V 2,S is the z-th wire in V 2 . C 2,S (y, z) = 0, otherwise.

V samples s 01 , s 2 ← $ Ŝ N so as to randomly combine P’s claims. Now, by running the sum-check protocol on Equation (32), P ends by claiming an evaluation µ+1 Ṽ 2 (r 2 ) (for a random sum-check challenge r 2 ← $ Ŝ N , since #(V 2 ) = µ + 1) which can be substituted into Equation (12) so as to advance towards the input layer.

s 01 Ṽ 2,d 01 (r d 01 ) + s 2 Ṽ 2,d 2 (r 2 ) = e s 01 C 2,d 01 (r d 01 , z) Ṽ 2 (z) + s 2

z∈{0,1} µ+1

e C 2,d 2 (r 2 , z) Ṽ 2 (z)

z∈{0,1} µ+1

Ṽ 2 (z) s 01 e C 2,d 01 (r d 01 , z) + s 2 e C 2,d 2 (r 2 , z) .

=

z∈{0,1} µ+1

For simplicity, the most significant variable of Ṽ 2 chooses between Ṽ 2,d 01 and Ṽ 2,d 2 , i.e. 11 Ṽ 2 (z [µ] , 0) = Ṽ 2,d 01 (z [µ] ) and Ṽ 2 (z [µ−1] , 1, 1) = Ṽ 2,d 2 (z [µ−1] ). Let us

It is arbitrary whether to have Ṽ 2 (z [µ−1] , 1, 1) = Ṽ 2,d 2 (z [µ−1] ) and Ṽ 2 (z [µ−1] , 0, 1) = 0 or viceversa.

<!-- page 70 -->

define the corresponding predicates. Notice that X is of length µ and Y is of length µ − 1.

e C 2,d 01 (X, Z) = (1 − Z µ ) · e f q(X, Z [0] ) e C 2,d 2 (Y, Z) = Z µ · Z µ−1 · e f q(Y, Z [1] )

While we could have defined Ṽ 2 directly as we just have described and use it to replace calls to Ṽ 2,d 01 and Ṽ 2,d 2 in Equations (7) and (11), that would have made our protocol more expensive. Had we done so, we would have required a standard two-to-one reduction in Equation (12), which requires twice the amount ^ predicates in there. Since those encode the “actual HE of queries to the Xmult circuit” and we implement them using polynomial commitments, we would rather do the simpler reassignment from Equation (32).

E.5

Prover algorithms

Here we list the necessary algorithms for a linear time prover when executing sumcheck on algorithms, adapted from Libra [XZZ + 19]. We take verbatim from there the following algorithms and their dependencies: Sumcheck (Algorithm 2), SumcheckProduct (Algorithm 3) and Precompute (given as a procedure within Algorithm 4). Notice that these algorithms represent polynomials as their evaluation at the set {0, 1, 2}, which has to be an exceptional set in R q in order to establish an isomorphism with their coefficient form. This is always the case for our choice of parameters, but otherwise {0, 1, 2} can be replaced with any other exceptional set of the same size. In all our algorithms, we start challenging from the least to the most significant variables. This has positive efficiency impacts due to the sparsity provided by prefixes in the MLEs of the wiring predicates (which are placed at their most significant position). Some of our algorithms exploit that kind of sparsity, as well as the possibility of multiplying vectors of different length. Algorithm 5 is one of the central pieces of our efficient proofs for R AC . It requires several subroutines, given in Algorithms 1 to 4. Throughout, we abbreviate the following partially evaluated factors:

V b pt (x) := Ṽ 3,ptxt (x [d] ) · g(r Y ), V b BD (x) := Ṽ 3,BD (x [δ] , r Z , x [δ,2δ) ),

[δ,µ−1)

V b rc (x) := Ṽ 3,rc 3 (x [δ] , r Z [δ,µ) , x δ ),

whose look-up tables we write T X V b

pt

## T X V b rc

T X Ṽ . 3,rc 3

:=

:= T X Ṽ

:= g(r Y ) · T X V 3,ptxt , T X V b

and

3,BD

BD

Moreover, inside Algorithms 4 and 5, once T, Z and Y are

\ 3 (x) and rescon all fixed to their challenges, we write copycon(x), \ bdcon \ 3 (x) \ ^ for the resulting functions of x alone (i.e. bdcon 3 (x) := bdcon 3 (r T , r Z [δ] , x), rescon \ 3 (x) := rescon ^ 3 (r T , r Z [δ] , x), copycon(x) \ := copycon(r ^ T , r Z [#(copy)] , x, r Y )). The rounds that challenge the X variables are collected in Algorithm 4, which

<!-- page 71 -->

Algorithm 5 calls once its look-up tables are in place. To simplify the writing, Algorithm 5’s description we use the SumcheckProduct algorithm in lines 5 and 6. In practice and in our implementation, those are replaced with a more efficient SparseSumcheckProduct version which appears in Algorithm 9.

Algorithm 1: Algorithm Init_copy_Y( copycon, ^ T X V 3,ptxt , r T , r Z )

Input : Sparse multi-linear copycon(T, ^ Z, X, Y). Multi-linear V 3,ptxt (X [d] ) and #(copy) its initial look-up table. Random challenges r T ∈ Ŝ N , r Z ∈ Ŝ N . Y Output: Look-up table T f 1 . 1 T r T ← Precompute(r T ). 2 T r Z ← Precompute(r Z ). m ′ Y 3 ∀y ∈ {0, 1} , set T f 1 [y] = 0. 2+#(copy)+m+m ′ such that copycon(t, ^ z, x, y) ̸ = 0, 4 For every (t, z, x, y) ∈ {0, 1} do: Y Y ^ z, x, y) · T X V 3,ptxt [x [d] ]. 5 T f 1 [y] ← T f 1 [y] + T r T [t] · T r Z [z] · copycon(t, Y 6 return T f 1

Algorithm 2: Algorithm Init_copy_X( copycon, ^ r T , r Z , r Y )

Input : Sparse multi-linear copycon(T, ^ Z, X, Y). Random challenges #(copy) m ′ , r Y ∈ Ŝ N . , r Z ∈ Ŝ N r T ∈ Ŝ N Output: Look-up table T X f 3 . 1 T r T [t] ← Precompute(r T ). 2 T r Z [z] ← Precompute(r Z ). 3 T r Y [y] ← Precompute(r Y ). m 4 ∀x ∈ {0, 1} , set T f 3 [x] = 0. 2+#(copy)+m+m ′ such that copycon(t, ^ z, x, y) ̸ = 0, 5 For every (t, z, x, y) ∈ {0, 1} do: ^ z, x, y). 6 T f 3 [x] ← T f 3 [x] + T r T [t] · T r Z [z] · T r Y [y] · copycon(t, 7 return T f 3

We invoke Init_X also on the intermediate-value MLEs Ṽ 3,BD and Ṽ 3,rc 3 , which carry no T variables and for which only part of their arguments comes from Z, their HE-level block being read from X [δ] . In every call we therefore pass exactly the block of challenges that the argument depends on: Init_X( Ṽ 3,BD , r Z [δ,µ−1) ) returns a table indexed by the 2δ variables X [2δ] (level and p i ), and Init_X( Ṽ 3,rc 3 , r Z [δ,µ) ) one indexed by the δ+1 variables X [δ+1] (level and the rmd-vs-quot bit). Likewise ^ 3 , rescon bdcon ^ 3 only depend on Z [δ] and e g vk on Z [δ+1] . The tables T X V 3,ptxt , T Y g and T Z Ṽ are not produced by Init_X: the polynomials they tabulate depend neither on T nor on any block of Z that is fixed to a

<!-- page 72 -->

Algorithm 3: Algorithm Init_X(f, r T , r Z )

Input : Multi-linear f (T, Z, X). Random challenges r T ∈ Ŝ N and r Z , the block of Z-challenges that f depends on. Output: Look-up table T X f . 1 T r T [t] ← Precompute(r T ). 2 T r Z [z] ← Precompute(r Z ). m 3 ∀x ∈ {0, 1} , set T f [x] = 0. 4 For every (t, z, x) in the domain of f such that f (t, z, x) ̸ = 0, do: 5 T f [x] ← T f [x] + T r T [t] · T r Z [z] · f (t, z, x). 6 return T f

challenge, so they are simply the initial bookkeeping tables of Ṽ 3,ptxt , g and Ṽ 2 , which the prover assembles from values it already holds.

Algorithm 4: Algorithm Sumcheck_X( copycon, \ T X f 3 , V b pt , T X Ṽ · 3,ptxt \ 3 , T X , rescon \ 3 , T X , V b rc , T X ) , V b BD , T X g(r Y ), bdcon

Ṽ 3,BD

^ b dcon 3

Ṽ 3,rc 3

rescon ^ 3

of the three wiring Input : The look-up tables T X f 3 , T X b ^ , T X rescon ^ 3 dcon

predicates and T X Ṽ 3,ptxt · g(r Y ), T X Ṽ , T X Ṽ 3,rc of the three factors 3,BD they are paired with, as built in Algorithm 5. Output: a [m ′ ,m+m ′ ] , which are the prover sumcheck messages for the X variables in Equation (7) 1 Comment: The three products are added up inside a single sumcheck, so their rounds must be interleaved rather than run one after the other: the message of round i is the sum of the three round-i contributions, and only once it has been sent is r X i available and the six look-up tables advanced by one variable. We write SumcheckProduct (i) for the i-th round of SumcheckProduct, that is, for the three elements (a i,0 , a i,1 , a i,2 ) it outputs in that round. Interleaving at the level of rounds is also what lets each product keep its own number of variables for the second term, namely d for Ṽ 3,ptxt , 2δ for Ṽ 3,BD and δ + 1 for Ṽ 3,rc 3 . 2 for i ← 0 to m − 1 do The next three steps are executed in parallel: a ′ m ′ +i ← SumcheckProduct (i) ( copycon(x), \ T X f 3 , V b pt (x), T X Ṽ 3,ptxt · g(r Y )) \ 3 (x), T X ) a ′′ m ′ +i ← SumcheckProduct (i) ( bdcon , V b BD (x), T X

Ṽ 3,BD

^ b dcon 3

(i) a ′′′ \ 3 (x), T X rescon , V b rc (x), T X Ṽ 3,rc ) m ′ +i ← SumcheckProduct ( rescon ^ 3

a m ′ +i ← a ′ m ′ +i + a ′′ m ′ +i + a ′′′ m ′ +i Send a m ′ +i , receive r X i ∈ Ŝ N and advance the six look-up tables with it, as FunctionEvaluations and SparseFuncEval do. 9 end 10 return a [m ′ ,m+m ′ ]

<!-- page 73 -->

Algorithm 5: Sumcheck Equation (7)

Output: a [m+m ′ ] , which are the prover sumcheck messages for Equation (7) Comment: We challenge first on the Y variables, then, in Algorithm 4, on the X ones. Notice the abuse of notation in lines 4 and 5, since Ṽ 3,BD and Ṽ 3,rc 3 have no T variables and only their wire-indexing block comes from Z. The abbreviations V b BD (x) and V b rc (x) are the ones introduced in Equation (33), ^ 3 and rescon and we drop the fixed arguments r T , r Z [δ] from bdcon ^ 3 . ^ 3 , r T , r Z [δ] ) 2 T ^ ← Init_X( bdcon

bdcon 3

## T X rescon ← Init_X( rescon ^ 3 , r T , r Z [δ] ) ^ 3

## T X Ṽ

← Init_X( Ṽ 3,BD , r Z [δ,µ−1) )

3,BD

5 T Ṽ ← Init_X( Ṽ 3,rc 3 , r Z [δ,µ) ) 3,rc 3 Y 6 T f 1 ← Init_copy_Y( copycon, ^ T X V 3,ptxt , r T , r Z [#(copy)] )

The next two steps are executed in parallel: P a ′ [m ′ ] ← SumcheckProduct( x∈{0,1} m copycon(r ^ T , r Z [#(copy)] , x, y) ·

Y Ṽ 3,ptxt (x [d] ), T Y f 1 , g(y), P T g , r Y ) b BD (x) + rescon b rc (x) \ bdcon (x) · V \ (x) · V 9 a [m ′ ] ← a [m ′ ] + 1 · m x∈{0,1}

T X f 3 ← Init_copy_X( copycon, ^ r T , r Z [#(copy)] , r Y ) 11 a [m ′ ,m+m ′ ] ← Sumcheck_X( copycon, \ T X f , V b pt , T X

· g(r Y ), Ṽ 3,ptxt b b \ 3 , T ^ , V BD , T bdcon , rescon \ 3 , T rescon , V rc , T X Ṽ 3,rc ) ^ 3 Ṽ 3,BD bdcon 3

^ 2 (r T ) · Ṽ 2,d 2 (r Z [µ−1] ) + rescon a [m+m ′ ] ← a [m+m ′ ] + bdcon ^ 1 (r T ) · Ṽ 1 (r Z [µ] ) − copycon ^ 3,copy (r T ) · Ṽ 3,copy (r Z [#(copy)] ) 13 return a [m+m ′ ]

Algorithm 6: Sumcheck Equation (11)

Output: a [2δ] , which are the prover sumcheck messages for Equation (11). Comment: The challenges r Z of this equation are those output by the sumcheck of Eq. (7) for Ṽ 1 . Still, the table of Ṽ 3,BD must be rebuilt from scratch, since the one from line 4 of Algorithm 5 is conditioned on a different block of Z. g 2 T evk f ← Init_X( evk, r Z [δ+1] )

## T X Ṽ

← Init_X( Ṽ 3,BD , r Z (δ,µ) )

3,BD

b g 4 a [2δ] ← SumcheckProduct( e vk(r Z [δ+1] , x), T X evk f , V BD (x), T Ṽ 3,BD , r X ) 5 a [2δ] ← a [2δ] + Ṽ 2,d 01 (r Z )

return a [2δ]

<!-- page 74 -->

Algorithm 7: Sumcheck Equation (32)

Output: a [µ+1] , which are the prover sumcheck messages for Equation (32). T e Z C ← Init_X( e C 2,d 01 , r d 01 )

2,d 01

T e Z C

← Init_X( e C 2,d 2 , r d 2 )

2,d 2

C 2,d 2 (r d 2 , z), s 01 T e Z C a [µ+1] ← SumcheckProduct(s 01 e C 2,d 01 (r d 01 , z) + s 2 e

s 2 T e Z C , Ṽ 2 (z), T Z Ṽ 2 , r Z ) 2,d 2

return a [µ+1]

+

2,d 01

For Equation (12), follow essentially SumCheckGKR from Libra [XZZ + 19].

Exploiting sparsity Function Evaluations for sparse polynomials There are different MLEs that we use in the algorithms above which are very sparse. In par- ^ 3 and rescon ticular, this is the case for bdcon ^ 3 . The former only has D(D +1)/2 non-zero evaluations in X, despite that vector being much longer and the latter, only 2D. Moreover, these predicates are sparse in a very structured way, where all non-zero entries share the all-one vector as a common prefix: the padding factors e f q(X [2δ,m) , 1) and e f q(X [δ+1,m) , 1) pin the L = m − 2δ, resp. L = m − δ − 1, most significant positions. Algorithm 8 shows how to compute the sumcheck messages for this functions more efficiently. Whenever FunctionEvaluations would be called upon these predicates, replace it with SparseFuncEval. Notice ^ 3 , rescon that whenever Algorithm 8 is called upon f ∈ { bdcon ^ 3 }, they have already become a function only in X variables, due to the previous execution of Init_X(f, r T , r Z [δ] ).

SumcheckProduct with different length and sparsity Using Algorithm 8, we construct a more efficient, sparse version of SumcheckProduct which we denote SparseSumcheckProduct and provide in Algorithm 9. This is a replacement for lines 5 and 6 in Algorithm 4.

<!-- page 75 -->

Algorithm 8: Algorithm SparseFuncEval(f (X 0 , . . . , X m−1 ), T f , L, r X )

Input : Multi-linear f and its initial bookkeeping table T f . Prefix length L, ? i.e. length of the all-one vector 1. Random challenges r ∈ Ŝ N . Output: All function evaluations for sumcheck. 1 for i ← 0 to m − 1 do if i < m − L then foreach b ∈ {0, 1} m−i−1 do for t ← 0 to 2 do f (r 0 , . . . , r i−1 , t, b [m−i−1] ) ← T f [0 [i] , 0, b [m−i−1] ] · (1 − t) + T f [0 [i] , 1, b [m−i−1] ] · t; end T f [0 [i+1] , b [m−i−1] ] ← T f [0 [i] , 0, b [m−i−1] ] · (1 − r i ) + T f [0 [i] , 1, b [m−i−1] ] · r i ; end end else if i ≥ m − L then for t ← 0 to 2 do f (r [i] , t, 1 [m−i−1] ) ← T f [0 [i] , 1 [m−i] ] · t end T f [0 [i+1] , 1 [m−i−1] ] ← T f [0 [i] , 1 [m−i] ] · r i ; end 16 end 17 Let F contain all function evaluations f (·) computed above. return F

Algorithm 9: Algorithm SparseSumcheckProduct(f, T X f , g, T X g , r)

Input : Multi-linear f (X 0 , . . . , X L−1 ), g(X [L ′ ] ) where L ′ < L. f is a sparse wiring predicate where non-zero values share the prefix in X. L . Random challenges r ∈ P Ŝ N Output: sumcheck messages for x f (x) · g(x [L ′ ] ) Each message a i,t consists of 3 elements. 1 F ← SparseFuncEval(f, T f , r X ). 2 G ← FunctionEvaluations(g, T g , r X [L ′ ] ). 3 for i ← 0 to L − 1 do for t = 0, 1, 2 do if i < L ′ then a i,t P = b [i+1,L) ∈{0,1} L−i−1 f (r 0 , . . . , r i−1 , t, b)·g(r 0 , . . . , r i−1 , t, b [i+1,L ) )

end else if L ′ P ≤ i < L then a i,t = b [i+1,L) ∈{0,1} L−i−1 f (r 0 , . . . , r i−1 , t, b) · g(r 0 , . . . , r L ′ −1 )

end end 12 end 13 return a = (a 0 , . . . , a L−1 )

<!-- page 76 -->

Putting everything together: The Π CKKS PIOP

F

We are finally in a position to define our global PIOP Π CKKS . In [CCC + 25], the final claimed values of Π AC were reduced to claims about D + 1 oracles: J Ṽ out K for the claimed ciphertext outputs, J Ṽ aux,2 u K for all non-deterministic inputs from the prover that need to be proven smaller than 2 u and finally, for j = 1, . . . , D − 1, J Ṽ aux,j K for non-deterministic inputs from the prover that need to be proven smaller than q/q L−j−1 . To those oracles, our richer arithmetization has added J Ṽ 3,ptxt K and J Ṽ 3,copy K. In the next section, we explain how the different oracles from our Π AC in Section 5.2 can be recombined so that we optimize our use of range proofs from Section 4 and polynomial commitments. In summary, J Ṽ aux,2 u K can be implemented from J Ṽ 3,rc 3 K, J Ṽ aux,j K from J Ṽ 3,BD K, J Ṽ 3,rc 3 K and J Ṽ out K from J Ṽ 3,rc 3 K, J Ṽ 3,copy K.

F.1

Rearranging into the final oracles and final queries

After executing the sumcheck protocol on Equation (12), we still need to match the syntax of Π AC given in Π CKKS . In [CCC + 25], claimed values were reduced to claims about D+1 oracles: J Ṽ out K for the claimed ciphertext outputs, J Ṽ aux,2 u K for all non-deterministic inputs from the prover that need to be proven smaller than 2 u and finally, for j = 1, . . . , D − 1, J Ṽ aux,j K for non-deterministic inputs from the prover that need to be proven smaller than q/q L−j−1 Rather than following the strategy from [CCC + 25], in our work we exploit existing relations between the oracles that were already employed during Π AC to produce the ones we need. This avoids the cost of one sumcheck to do recombinations and reassignments [CCC + 25, Eq (23)], together with the computation of the relevant reassigning predicates by both the prover and the verifier. Moreover, it also requires less queries.

1. Given the oracle J Ṽ 3,rc 3 K, we have implicit access to J Ṽ 3,quot K, so we don’t need to split it. Given a query Ṽ 3,quot (x [quot] ), translate it to Ṽ 3,rc 3 (x [quot] , 1). Following the same idea, we can also produce oracles J Ṽ aux,j K D−1 j=1 : Given a query Ṽ aux,j (x [#(aux,j)] ), it can be answered with Ṽ 3,rc 3 (bin(j), x [#(aux,j)] , 1). 2. Going in the opposite direction, we can also avoid using sumcheck to recombine J Ṽ 3,BD K, J Ṽ 3,rc 3 K into a single oracle J Ṽ aux,2 u K. Instead, we create a virtual oracle that includes the two smaller ones. All values in J Ṽ 3,BD K would belong to J Ṽ aux,2 u K, whereas for J Ṽ 3,rc 3 K the legal queries are those of the form Ṽ 3,rc 3 (0, x [µ] ). Let Z = (Z 0 , . . . , Z µ+δ−1 ). The following MLE shows us how to query the virtual oracle (we are assuming δ ≥ 1):

Ṽ aux,2 u (Z) = (1 − Z µ+δ−1 ) · Ṽ 3,BD (Z [µ+δ−1] ) + Z µ+δ−1 · Ṽ 3,rc 3 (Z [µ] , 0)

3. Finally, the Ṽ out oracle can also be easily implemented by querying directly J Ṽ 3,rc 3 K or J Ṽ 3,copy K at the relevant wire that has to be revealed.

<!-- page 77 -->

4. Hence, merely by implementing J Ṽ 3,copy K, J Ṽ 3,rc 3 K and J Ṽ 3,BD K through a polynomial commitment, we can verify all claimed values Ṽ 3,quot (r quot ), Ṽ 3,quot (r ′ quot ), Ṽ 3,BD (r BD ), Ṽ 3,rc 3 (r rc 3 ), Ṽ 3,copy (r copy ) and Ṽ 3,copy (r ′ copy ) as well as we can perform the necessary range checks. Moreover, we apply a final optimization: we implement the three oracles as a single PC with 2 + max(#(copy), µ + 1, µ + δ − 1) variables. This can be done using the same idea as when we defined J Ṽ aux,2 u (Z)K

Auxiliary Material on SparsePack

G

Our SparsePack PIOP for Evaluating Sparse Polynomials

G.1

In this section, we provide a full description of SparsePack. Precisely, we denote by SparsePack-Π iptree its version that internally relies on a PIOP Π iptree .

SparsePack Indexer. On input the relation’s index (p 0 , . . . , p a−1 ), define the (≤1) polynomial pol ∈ Z q [X 1 , . . . , X ℓ , T 1 , T 2 , Z 1 , . . . , Z α+µ ] such that, for all b ∈ ℓ α {0, 1} , i ∈ {0, 1} , j ∈ {0, 1} µ and j ′ ∈ {0, 1} µ−1 :

pol(b, 0, 0, i, 0) = val(b, i)

pol(b, 1, 0, i, j) = ind(b, i, j)

pol(b, 1, 1, i, j ′ , 0) = ind(b, i, j ′ , 0) · ind(b, i, j ′ , 1),

pol(b, 1, 1, i, j ′ , 1) = 0

and pol is 0 on all the remaining points of {0, 1} ℓ+2+α+µ . Note that, by multilinearity, the following identities hold as polynomials, where ind ∗ is defined as in Section 6:

pol(X, 1, 1, Z [1,α+µ−1] , 0) = ind ∗ (X, Z [1,α+µ−1] ).

pol(X, 1, 0, Z) = ind(X, Z),

(≤1)

The indexer returns i = JpolK, where pol = pack(pol) ∈ R q n = ℓ + 2 + α + µ − ν.

SparsePack-Π iptree online phase.

[X 1 , . . . , X n ] and

α 1. V sends t ← $ Ŝ N . 2. P and V run Π iptree for ((ỹ(t), JvalK, Jf 2 K, JE µ−1 K); val, f 2 , E µ−1 ) ∈ R iptree , ˜ where pol = unpack(pol), val = pol(X, 0, 0, Z [1,α] , 0), f 2 = eq(X, t), and E µ−1 is as in equation (15). 3. Let Π iptree .V’s queries be: (r 1 , r ′ 1 ) to JvalK, r 2 to Jf 2 K, and (r, s) to JE µ−1 K. P sends ψ val = val(r 1 , r 1 ), ψ 0 = ind(r, s, 0), ψ 1 = ind(r, s, 1), and ψ ∗ = ind ∗ (r, s). ˜ 2 , t) on its own, and the query V answers the query to Jf 2 K by computing eq(r to JE µ−1 K by computing, according to equation (15),

ψ = ψ 0 · x̃ ∗ 0 (s) + ψ 1 · x̃ ∗ 1 (s) + ψ ∗ · x̃ ∗ 2 (s) + x̃ ∗ 3 (s).

<!-- page 78 -->

4. V sends random τ, ζ ← $ Ŝ N . 5. V computes ψ pol = (ψ 0 · (1 − ζ) + ψ 1 · ζ) · (1 − τ ) + ψ ∗ · (1 − ζ) · τ . Note that if ψ 0 , ψ 1 , ψ ∗ are correct then ψ pol = pol(r, 1, τ, s, ζ), by the layout of pol fixed by the indexer and the multilinearity of pol in T 2 and Z α+µ . (κ) P and V run the PIOP Π ueval on ((ψ val , x val , ψ pol , x pol , JpolK); pol) ∈ R ueval where x val = (r 1 , 0, 0, r ′ 1 , 0) and x pol = (r, 1, τ, s, ζ). (κ) Π ueval ends with the verifier querying JpolK on ρ 1 , . . . , ρ κ ∈ Z nq .

We refer to Section 6 for an intuitive explanation of the protocol. Here we provide an additional intuition on the last part of the protocol that deals with evaluating the unpacked polynomial pol. Our solution requires querying the unpacked JpolK on points in R q , meaning that we cannot use the result of Lemma 3 to compute them from queries to JpolK. The last piece of the protocol, which solves this issue, is the use of our PIOP Π ueval of Section 3.2 for proving evaluations of unpacked polynomials on R q points. An alternative idea to avoid the use of Π ueval and instead use Lemma 3 might have been to instantiate Π iptree so as to use random challenges in the exceptional set Ŝ 0 ⊂ Z q . This change would lead to querying pol on points of Z q . However, it would yield no gain in communication since the sumcheck of equation (14) involves x̃, which encodes the evaluation inputs that are in R q . Thus using challenges in Ŝ 0 would still require the prover to send full R q elements in every round of the sumcheck, in addition to the fact that such a sumcheck, with R q -dependent communication size, would need to be repeated several times to achieve a desired level of RBR-soundness. Next, we state and prove the security of SparsePack.

Theorem 10. Let Π ueval be the PIOP for R ueval of Section 3.2, and let Π iptree be a PIOP for R iptree (with β = µ − 1) with δ-knowledge-soundness. Then SparsePack-Π iptree is a PIOP for R speval with δ speval -knowledge soundness where δ speval = δ + (α + 2)/| Ŝ N | + ((2n + 5ν + 1)/| Ŝ 0 |) κ , where n = ℓ + α + µ + 2 − ν is the number of variables of pol.

Proof. Assume we start with a false statement ( i , x ) ∈ / L(R speval ). Then the polynomial identity of equation (13) does not hold and, since both its sides are multilinear in Z, the probability over the choice of t that the equality of equation (14) holds is ≤ α/| Ŝ N |. Assume that equation (14) does not hold, let ψ val , ψ 0 , ψ 1 , ψ ∗ be the values sent by the prover in step 3, and let ψ be the value computed by the verifier from them. If ψ 0 = ind(r, s, 0), ψ 1 = ind(r, s, 1), and ψ ∗ = ind ∗ (r, s), then ψ = E µ−1 (r, s) by equation (15). Hence the probability that the verifier accepts in Π iptree , conditioned on ψ 0 , ψ 1 , ψ ∗ being correct and ψ val = val(r 1 , r ′ 1 ), is ≤ δ by the soundness of Π iptree . If any of ψ 0 , ψ 1 , ψ ∗ is wrong, then ψ pol − pol(r, 1, τ, s, ζ) is a nonzero polynomial of total degree 2 in (τ, ζ), hence ψ pol = pol(r, 1, τ, s, ζ) holds with probability at most 2/| Ŝ N | over the choice of τ, ζ.

<!-- page 79 -->

Finally, if ψ pol ̸ = pol(r, 1, τ, s, ζ) or ψ val ̸ = pol(r 1 , 0, 0, r ′ 1 , 0) = val(r 1 , r ′ 1 ) (κ) then the verifier accepts in Π ueval with probability at most ((2(ℓ + α + µ + 2) + 3ν +1)/| Ŝ 0 |) κ = ((2n+5ν +1)/| Ŝ 0 |) κ , by Theorem 1 (applied to a = 2 evaluation points of a packed polynomial with n variables) and Theorem 4. Furthermore, using a similar proof, if Π iptree has RBR-soundness δ ′ , then we can argue the RBR-soundness of SparsePack-Π iptree to be the maximum of

α

, δ , δ 4 ′ =

δ 1 ′ =

,

| Ŝ N |

| Ŝ N |

κ ! n+ν

2n + 5ν + 1

.

| Ŝ 0 |

Instantiations of SparsePack and Efficiency

G.2

To obtain SparsePack we instantiate Π iptree with a PIOP that uses Thaler’s approach for proving a tree of multiplications [Tha13], adapted to work for 2 ℓ+α trees of multiplications of depth µ − 1, done in parallel, followed by an inner product. We refer to the next section for more details on this protocol. Here we recall that it can be proven by performing µ − 1 sequential sumchecks of increasing width 2 ℓ+α+η , for η = 0 to µ − 2, which, as required by Π iptree , end up with the verifier querying the polynomials val(r 1 , r ′ 1 ), E µ−1 (r, s), and ˜ 1 , t). The query to E µ−1 (r, s) is answered by the verifier itself computing eq(r from the values ψ 0 = ind(r, s, 0), ψ 1 = ind(r, s, 1), and ψ ∗ = ind ∗ (r, s) sent by the prover, so no additional sumcheck is needed. Finally, all these queries are (κ) proven with an execution of Π ueval . In total, SparsePack’s communication consists of 4ℓ(µ − 1) + (4µ − 1)α + 2µ 2 − 2µ + 2 elements of H q (see the paragraph on diagonal challenges below), κ(4(ℓ + α + µ) + 1) elements of Z q , and one PC evaluation proof for a polynomial of ℓ + α + µ + 2 − ν variables. We compare SparsePack with Spark, as specified in Spartan [Set20], with the counter polynomials produced and committed in preprocessing, and with c dimensions as in [STW24]. We compile it with the PC transform for R q of [CCC + 25] over Basefold, i.e., one BaseFold PC on each CRT component of R q , without batching across them. As in Spartan, the grand products of all the multiset checks are proven as a single data-parallel layered circuit [Tha13], with one sumcheck per layer. For c = ⌈m/ℓ⌉, this solution would require: 3 · a · c committed polynomials of size 2 ℓ in the preprocessing, a · c committed polynomials of size 2 ℓ generated at proving time, an overall communication of (c + 2)ℓ + 2(⌈log c⌉ + α + 1)ℓ(ℓ − 1) + 2ℓ elements of R q , and the PC evaluation proofs for 4ac multilinear polynomials of ℓ variables, queried at two points, which we batch into two Basefold evaluation proofs [ZCF24]. To obtain a concrete comparison, we consider the following parameters, N = 2 13 , log q ≈ 135, ℓ = 15, m = 34, a = 2, which correspond to the largest circuit of one of our neural networks applications (see Section 8). Even ignoring the size of PC evaluation proofs, SparsePack’s proof is 25.4 KiB, against 235.3 MiB for Spark. More interestingly, SparsePack avoids altogether running the PC on large polynomials: it does not generate any commitment

<!-- page 80 -->

during the proof, and it computes a single evaluation proof for the preprocessed (packed) polynomial pol that, thanks to packing, has only 11 variables; using our new BatchFold scheme this proof is 163 MiB and, together with Π ueval , takes about two minutes to compute. In contrast, Spark prover has to commit to 6 polynomials of size 2 15 (which takes about 10 minutes) and prove evaluations of 4ac = 24 polynomials of size 2 15 . Using two batched Basefold proofs over R q as in [CCC + 25], these evaluations would take a total of about 7 minutes, yielding a proof of 6.2 GiB.

Diagonal challenges. The figures above and Table 2 take the verifier’s challenges in Ŝ N from its diagonal copy of H q , i.e., one element of F p di repeated in the N/d slots of each p i . This was already the case in [CCC + 26b], but the protocol there did not exploit it. Since all the points at which the sparse polynomials are evaluated are then diagonal, every table of Π iptree lies in the diagonal subring of R q , which is isomorphic to H q : its sumchecks run over H q and send elements of H q , N/d times smaller than those of R q , and the evaluation proof of pol needs no common-point sumcheck. Without this, the sumchecks of SparsePack would take 28m13s, 3m28s and 1m44s for our three circuits (instead of about one second) and send 50.8, 35.5 and 33.4 MiB; SparsePack would then be 0.7×, 1.4× and 1.3× as fast as Spark (instead of 10.6×, 23.5× and 11.2×), and still 28–31× shorter. The same choice gives the prover of Π ueval the time O(a2 ℓ+ν ) of Theorem 1: at points that are not diagonal, building its table E directly could take N times more operations in Z q .

Details on our instantiation of Π iptree

G.3

In this section we give more details on how to instantiate our application of the Π iptree PIOP using Thaler’s approach for trees of multiplications. Consider the polynomial E µ−1 (X, Z, Z ′ ) that is of degree 1 in X and degree 2 in (Z, Z ). Let Ẽ µ−2 be the multilinear polynomial such that

∀(b, i, j) ∈ {0, 1} ℓ+α+µ−2 : Ẽ µ−2 (b, i, j) = E µ−1 (b, i, j, 0) · E µ−1 (b, i, j, 1)

Next, for η = µ − 3 down to 1, let Ẽ η be the multilinear polynomial such that

∀(b, i, j) ∈ {0, 1} ℓ+α+η : Ẽ η (b, i, j) = Ẽ η+1 (b, i, j, 0) · Ẽ η+1 (b, i, j, 1)

K); val, f 2 , E µ−1 ) ∈ R iptree runs µ − 1 Then Π iptree on ((ỹ(t), JvalK, Jf 2 K, JE µ−1 ℓ+α+η sumchecks, sequentially, of increasing width 2 , for η = 0 to µ − 2. This proceeds as follows. For η = 0, it starts with a sumcheck of width 2 ℓ+α and degree 3 in ℓ variables and 4 in α variables, for the claim ỹ(t) = val(b, i)f 2 (i) · Ẽ 1 (b, i, 0) · Ẽ 1 (b, i, 1)

(b,i)∈{0,1} ℓ+α

Its communication is 4ℓ + 5α + 2 elements of R q , and it ends with a “promise” claim v 1 = Ẽ 1 (r 1 ).

<!-- page 81 -->

For η = 1 to µ − 3, it runs a sumcheck of width 2 ℓ+α+η and degree 3 in all ℓ + α + η variables, for the claim ˜ v η = Ẽ η+1 (b, i, j, 0) · Ẽ η+1 (b, i, j, 1) · eq((b, i, j), r η )

(b,i,j)∈{0,1} ℓ+α+η

Its communication is 4(ℓ+α+η)+2 elements of R q , and it ends with a “promise” claim v η+1 = Ẽ η+1 (r η+1 ). For η = µ−2, it runs a sumcheck of width 2 ℓ+α+µ−2 of degree 3 in ℓ variables and 5 in α + η variables, for the claim ˜ E µ−1 v µ−2 = (b, i, j, 0) · E µ−1 (b, i, j, 1) · eq((b, i, j), r η )

(b,i,j)∈{0,1} ℓ+α+µ−2

Its communication is 4ℓ + 6(α + µ − 2) + 2 elements of R q , and it ends with the claim ψ = E µ−1 (r, s). Therefore the total communication of this protocol is 4ℓ(µ − 1) + (4µ − 1)α + 2µ 2 − 2µ − 2 elements of R q .

Details about BaseFold

H

In this section we describe the BaseFold polynomial commitment, and our protocol Eval com M for batched openings at a common point built on top on it, in detail. Moreover, we show a slight improvement on the lower bounds for the minimum distance of the codes involved, that translates into a better soundness error.

H.1

The BaseFold Error Correcting Codes

The central component of the BaseFold polynomial commitment is a probabilistic construction of a family of linear codes. Starting from a fixed code C 0 , the procedure constructs {C i } i∈N such that the length and dimension of C i are double the ones from C i−1 . Thus, if k i and n i respectively denote the dimension and length of C i , we have that k i = 2 i k 0 and n i = 2 i n 0 . For each i, a vector t i−1 is chosen uniformly at random in (F ∗ ) n i−1 (once and for all). The encoding function Enc i with code C i is then defined from Enc i−1 and t i−1 as described in Figure 11.

H.2

The BaseFold Commitment and Evaluation

In order to commit to a multilinear polynomial f in F[X 1 , . . . , X ℓ ], we set up a family of codes {C i } di=0 as above such that k 0 = 2 ℓ 0 and d = ℓ − P ℓ 0 . Note that k d = 2 ℓ , which is the number of coefficients of f . We identify f = j∈{0,1} ℓ f j X j with the vector f ∈ F k d given by f [to-int(j)] = f j . The commitment to f is then π d , an oracle to Enc d (f ), which in practice will be instantiated with a vector commitment such as a Merkle-tree based commitment.

<!-- page 82 -->

Encoding algorithm for C i in Basefold

Recursive encoding function Enc i for messages in F k i , with k i = 2 i k 0 . It requires to have fixed a [n 0 , k 0 ]-linear code C 0 with generator matrix G 0 ∈ F k 0 ×n 0 , and for each j < i, a vector t j ∈ (F ∗ ) n j (where n j = 2 j n 0 ).

- If i = 0, then Enc 0 (m) = mG 0 ∈ F n 0 - Else if i > 0 the encoding of m = (m L , m R ) ∈ F k i where m L , m R ∈ F k i−1 is given by

Enc i (m) =

(Enc i−1 (m L ), Enc i−1 (m L )) + (Enc i−1 (m R ), Enc i−1 (m R )) ◦ (t i−1 , −t i−1 )

where ◦ denotes the componentwise product. In other words Enc i (m) = mG i , where the generator matrix G i of C i is G i−1 G i−1 G i = G i−1 · T i−1 G i−1 · −T i−1

where T i−1 ∈ F n i−1 ×n i−1 is the diagonal matrix with diagonal t i−1 .

Figure 11: Encoding algorithm for C i in Basefold

Rather than describing the protocol Eval from [ZCF24] for a single opening of a committed polynomial, we already incorporate our additional steps to obtain Eval com M , the protocol that simultaneously proves the correct evaluation of M committed polynomials at the same point; the original Basefold evaluation protocol can be retrieved as the case M = 1. Concretely the protocol PC.Eval com M is a proof for the following relation:

−1 M −1 M −1 R Eval com = ((z, (y m ) M m=0 , (π d,f m ) m=0 ); (f m ) m=0 ) : M

π d,f m oracle to Enc d (f m ) ∧ f m (z) = y m , ∀m ∈ [M ]}

The protocol PC.Eval com M can be found in Figure 12. We now prove that the soundness of PC.Eval com M .

Lemma 9 (Lemma 5 restated). Fix a finite field F an d let {C i } di=0 linear codes over F be defined as above. If error PC.Eval com and error PC.Eval denote M respectively the soundness error of PC.Eval com and PC.Eval then error PC.Eval com ≤ M M M −1 |F| + error PC.Eval .

Proof. We note that steps 2-9 are a proof PC.Eval = PC.Eval com for the claim that P M −1 m P M −1 m (z, y ′ , π d,u ) ∈ L(R Eval com ) where y = s y and π = m d,u m=0 s π d,m m=0 where π d,m are the oracles in the initial statement. Hence it is enough to show that if the received starting claim is false, i.e. −1 M −1 (z, (y m ) M / L(R Eval com ) then (z, y ′ , π d,u ) ∈ L(R Eval com ) can hapm=0 , (π d,m ) m=0 ) ∈ M pen with probability at most (M − 1)/|F| over the choice of s.

<!-- page 83 -->

PC.Eval com M : Batched opening proof at common point z

Inputs: oracles π d,f m , evaluations y m , m ∈ [M ], and evaluation point z ∈ F ℓ . Proof that f m (z) = y m , m ∈ [M ].

1. If M > 1, the P verifier selects s ∈ F, sends it to the prover. The prover M −1 m sets u(X) := m=0 s f m (X). This implicitly defines π d := π d,u = P M −1 m s π . Else, if M = 1, define π d := π d,f 0 , u := f 0 d,f m m=0 2. For i = d − 1, . . . , 1, (a) The verifier selects α i ∈ F uniformly at random and sends it to the prover. (b) The prover constructs π i = (g 1 (α i ), . . . , g n i (α i )) where g j (X) is the unique polynomial of degree 1 with g j (t i [j]) = π i+1 [j] and g j (−t i [j]) = π i+1 [j+n i ]. (c) If i > 0, the prover sends oracle π i to the verifier. (d) In addition, the prover constructs the univariate polynomial h i (X) = u(b, X, α i , . . . , α d−1 ) · e f q((b, X, α i , . . . , α d−1 ), z)

b∈{0,1} ℓ 0 +i−1

and sends h i (X) to the verifier. 3. The verifier selects α 0 ∈ F uniformly at random and sends it to the prover. 4. The prover sends m, the vector of coefficients of the ℓ 0 -variate polynomial u(X 1 , . . . , X ℓ 0 , α 0 , . . . , α d−1 ). 5. The verifier computes π 0 = Enc 0 (m). 6. The verifier now verifies the validity of the commitment by executing rp times the following check. For ι in 1, . . . , rp: (a) Samples µ := µ ι ∈ [1, . . . , n d−1 ] (b) For each i = d − 1, . . . , 0: i. Queries π i+1 [µ] and π i+1 [µ + n i ] if they have not been queried before. If M > 1, the queries with i = d − 1 are carried out by querying all P M −1 m −1 (π d,f m [µ], π d,f m [µ + n i ]) M m=0 and defining π d [µ] = m=0 s π d,f m [µ] and analogously with π d [µ + n i ]. ii. Constructs g µ (X) from π i+1 [µ] and π i+1 [µ + n i−1 ] as above. iii. Queries π i [µ] and checks g µ (α i ) = ? π i [µ]. iv. Updates µ to (µ mod n i−1 ). 7. The verifier checks h 1 (α 0 ) = ? u(b, α 0 , . . . , α d−1 ) · e f q((b, α 0 , . . . , α d−1 ), z),

b∈{0,1} ℓ 0

using the received m to compute the evaluations of f on the right hand side. 8. The verifier also checks

h d (0) + h d (1) = ?

and

M −1

s m y m

m=0

h i (0) + h i (1) = ? h i+1 (α i )

for i ∈ [1, . . . , d − 1] 9. The proof is accepted if all checks pass.

Figure 12: PC.Eval com M : Batched opening proof of M evaluations at common point for the Basefold Polynomial Commitment.

<!-- page 84 -->

Assume the claim is false, then there is some m ∈ [M ] such that either π d,m is not a valid oracle to Enc d (f m ) for some f m ∈ F k d or f m (z) ̸ = y m for the associated f m . First suppose that for some m, π d,f m is a oracle to a vector v m ∈ / C d . Consider a parity check matrix H ∈ F (n d −k d )×n d i.e. a matrix H such that for every c ∈ F n d , c ∈ C d iff Hc = 0. Consequently since v m P ∈ / C d there is a row M −1 H i of H with H i v m ̸ = 0. Then the polynomial h(T ) = m=0 (H i v m ) · T m is nonzero, so it has at most M − 1 roots and hence P r[h(s) = 0] ≤ (M − 1)/|F| when s is sampled uniformly at random in F. But if h(s) ̸ = 0, then by linearity P M −1 P M −1 H i ( m=0 s m v m ) ̸ = 0 so m=0 s m v m ∈ / C d and therefore π d,u is not an oracle to a codeword in C d , so (z, y ′ , π d,u ) ∈ / L(R Eval com ). Otherwise for all m, π d,m is a oracle to some Enc d (f m ), and clearly π d,u is an P M −1 oracle to Enc d (u) with u = m=0 s m f m . Since the claim is false, f m (z) ̸ = y m for some m. Then in an analogous way as before, the polynomial h ′ (T ) := P M −1 m is nonzero so Pr[h ′ (s) = 0] ≤ (M − 1)/|F| when s m=0 (f m (z) − y m )T is sampled uniformly at random in F, while if h ′ (s) ̸ = 0 we have u(z) = P M −1 m / L(R Eval com ). m=0 s f m (z) ̸ = y , so again (z, y , π d,u ) ∈

Now we retrieve the soundness result obtained in BaseFold. The soundness error depends on the relative minimum distance ∆ C i of the codes C i defined as ∆(C i ) = d min (C i )/n i

Theorem 11 (Soundness of Basefold (case M = 1), from [ZCF24]). Let {C i } di=0 , the linear codes constructed above, and γ, δ ∈ (0, 1) satisfy p the conditions 12 δ < J γ (J γ (∆ C d )) and 3δ − dγ < ∆ C d , where J γ (x) := 1 − 1 − x(1 − γ). Then the soundness error of PC.Eval satisfies

2d

error PC.Eval ≤

γ 3 |F|

+ (1 − δ + γd) rp

Corollary 1. In the same conditions as above, the soundness error of error PC.Eval com M satisfies 2d M − 1 + 3 + (1 − δ + γd) rp error PC.Eval com ≤ M |F| γ |F|

The size of the proof, assuming we instantiate the oracles π i with Merkle commitments to vectors of length n i = 2 i · n 0 with hash functions of output size κ bits, is:

(2rp log n 0 (M + 1) + 2rpM d + rp(d − 1)d) κ+[3(d−1)+2rp(M +d−1)+2 ℓ 0 ] log |F|

bits. If we consider ℓ 0 and n 0 small, so d ∼ ℓ, and considering that for security parameter λ we need log |F|, κ, rp = O(λ), this is O (M ℓ + ℓ 2 )λ 2

Note that [ZCF24] states ∆ C i+1 ≤ ∆ C i for all i ∈ [0, d−1] as an additional condition, but this is always satisfied in the stated code construction

<!-- page 85 -->

communication. Compare this with naively computing M individual proofs for Basefold. The communication complexity in that case would be O M ℓ 2 λ 2 .

H.3

Improvements on the minimum distance estimates of the BaseFold codes

The security of the Basefold commitment depends on the relative minimum distance ∆ C i = d min (C i )/n i of the codes C i . We state next a lower bound on the minimum distance of these codes which is a slight improvement with respect to the one stated in [ZCF24].

Theorem 12. Let λ ∈ N. Define {C i } i∈N as above, with the additional assumption that C 0 is a MDS code (i.e. d min (C 0 ) = n 0 − k 0 + 1). For every d ∈ N,

Pr[d min (C d ) ≤ n d − t d ] ≤ d · 2 −λ

where t 0 = k 0 , and for every i > 0, t i = 2t i−1 + ℓ i with

|F| )) + 0.585n i λ + 2t i−1 (1 + log( |F|−1

ℓ i =

.

log(|F| − 1) − 1

The probability above is over the uniform choices of t i ∈ (F ∗ ) n i , i = 0, . . . , d − 1, in the definition of the codes. For |F| ≥ 2 11 , we can set

λ + 2.002t i−1 + 0.585n i . log |F| − 1.001

ℓ i =

For comparison, in [ZCF24, Theorem 2], the corresponding ℓ i (for a sufficiently large field) is given as

2(i − 1) log n 0 + λ + 2.002t i−1 + 0.6n i log |F| − 1.001

ℓ i =

which is less tight. In the remaining of this section, we prove this result. For our proof we will restate the results of [ZCF24] using a more code-theoretic notation, that uses the notion of shortened code. This also simplifies somewhat the proofs. For n > 0 and S ⊆ [n] we denote π S : F n → F |S| the projection to the coordinates in S. Given S ∈ [n] we write S̄ := [n] \ S for its complementary. We denote the Hamming weight of vector v as w Ham (v). Recall that a [n, k, d] q -linear code C is a linear code C over F q of length n, dimension k (i.e. cardinality q k ) and minimum distance d min (C) = d.

Definition 8 (C shortened at S). Given a code C ⊆ F n , the shortening of C at S (or C shortened at S) is the code C S = {π S̄ (c) : c ∈ C, π S (c) = 0}. I.e. the code that we obtain by restricting to the codewords in C that are 0 in all the coordinates in S and then removing these 0-coordinates.

<!-- page 86 -->

Lemma 10. If C is a [n, k, d] q -linear code, then if C S is a [n − |S|, k S , d S ] q linear code such that k S ≤ k and, if C S ̸ = {0}, d S ≥ d.

Proof. It is obvious that C S is of length n − |S|, and that k S ≤ k because the amount of codewords can only decrease. If C S ̸ = {0}, there is some nonzero codeword in w ∈ C S which means there is a nonzero codeword c in C with π S (c) = 0, π S̄ (c) = w ̸ = 0. Then clearly d ≤ w H (c) = w H (π S̄ (c)) = w H (w) so indeed d S ≥ d.

Lemma 11 (Singleton bound). For any [n, k, d] q -linear code C, we have k + d ≤ n +1

Proof. Well known fact in code theory.

Definition 9 (MDS code). A MDS code is a [n, k, d] q -linear code C with k + d = n + 1.

Definition 10. Let S ⊆ [n d−1 ]. We define m d (S) as the set of pair of codewords in C d−1 such that they have common zeros exactly in the coordinates of S, i.e.

m d (S) := {(c, c ′ ) ∈ (C d−1 ) 2 : ∀i ∈ S, c[i] = c ′ [i] = 0

∀i ∈ / S, c[i] ̸ = 0 ∨ c ′ [i] ̸ = 0}

Note (C d−1 ) 2 is the disjoint union of m d (S) for S ⊆ [n d−1 ], as every pair of codewords belongs to exactly one m d (S).

We now offer a proof of Lemma 2 in [ZCF24] that we consider is slightly simpler, using the coding-theory definition and facts above.

Lemma 12. [Lemma 2 in [ZCF24]]. Suppose d min (C d−1 ) > n d−1 − t for some t. Let S ⊆ [n d−1 ]. Then:

- If t ≤ |S| < n d−1 , then |m d (S)| = 0. - If |S| < t, then |m d (S)| ≤ |F| 2t−2|S| .

Proof. First, note |m d (S)| ≤ (|(C d−1 ) S |) 2 , where (C d−1 ) S is C d−1 shortened at S S. It is not necessarily an equality, because a codeword in C d−1 may be 0 in some coordinates of S̄. Then:

- If |S| ≥ t, m d (S) = 0, unless S = [n d−1 ] for which m d (S) = 1 Indeed, because d min (C d−1 ) > n d−1 − t there are no nonzero codewords in C d−1 with t zeros, and (0, 0) ∈ m d ([n d−1 ]). - If |S| < t, m d (S) ≤ |F| 2t−2|S| . Indeed in this case, either (C d−1 ) S = {0} and then m d (S) = 1 or (C d−1 ) S ̸ = {0}. Then (C d−1 ) S is a code of length n d−1 −|S| and distance d min ((C d−1 ) S ) ≥ d min (C d−1 ) ≥ n d−1 − t + 1. Then, by the Singleton bound,

dim(C d−1 ) S ≤ (n d−1 − |S|) − d min ((C d−1 ) S ) + 1 ≤ t − |S|.

Consequently

m d (S) ≤ |(C d−1 ) S | 2 ≤ (|F| t−|S| ) 2 .

<!-- page 87 -->

Now we work towards the improvement on the lower bounds. The following lemma shaves off a factor n d−1 with respect to Lemma 3 in [ZCF24]. The improvement stems from a better bound on the expression (35). Up to that point the proof is as in [ZCF24].

Lemma 13. [Improvement on Lemma 3 in [ZCF24]] Let S ⊆ [n d−1 ], (c, c ′ ) ∈ m d (S). Let ĉ = (c + c ′ ◦ t d−1 , c − c ′ ◦ t d−1 ) where t d−1 is chosen uniformly at random in (F \ {0}) n d−1 . Then for 0 < t ≤ n d , t−2|S| n d−1 −|S| Pr[w H (ĉ) ≤ n d − t] < 2 · |F| − 1

where the probability is over the choice of t d−1

Proof. For all i ∈ [n d−1 \ S], either c[i] ̸ = 0 or c ′ [i] ̸ = 0. For the sake of notation let a i := c[i], b i = c ′ [i], u i = t d−1 [i] Then the Hamming weight of the pair of coordinates (ĉ[i], ĉ[n d−1 + i]) is ( 1 if a i ̸ = 0 and u i = ±b i /a i w Ham (a i + b i · u i , a i − b i · u i ) = 2 otherwise

Note that the weight cannot be 0 as this would imply u i = 0, but t d−1 is sampled from (F \ {0}) n d−1 . The case 1 above happens with probability at most |F|−1 over the random choice of u i , and then case 2 happens with probability at least 1 − |F|−1 . Since all u i for i ∈ / P S are chosen independently, we have that the Hamming weight w Ham (ĉ) = i ∈S / w Ham (ĉ[i], ĉ[n d−1 + i]) is distributed according to a sum of independently distributed Bernouilli variables X i , with Pr[X i = 1] ≤ |F|−1 , Pr[X i = 2] = 1 − Pr[X i = 1] ≥ |F|−1 . To simplify, and since we are upper bounding the probability of w Ham (ĉ) being smaller than some quantity, we define X i ′ the Bernouilli variable with exact probabilities Pr[X i ′ = 1] = |F|−1 , Pr[X i = 2] = 1 − |F|−1 and we have Pr[w H (ĉ) ≤ n d − t] ≤ Pr[ X i ′ ≤ n d − t.]

i ∈S /

Moreover, we can write X i ′′ = 2 − X i ′ (hence Pr[X i ′′ = 1] = |F|−1 , Pr[X i ′′ = 0] = P P P ′′ 1− |F|−1 ) and we have i ∈S / X i = 2(n d−1 −|S|)− i ∈S / X i , so i ∈S / X i ≤ n d −t P ′′ if and only if i ∈S i ≥ 2(n d−1 − |S|) − (n d − t) = t − 2|S|. Hence we want an / X P ′′ upper bound for Pr[ i ∈S / X i ≥ t − 2|S|]. Now

n d−1 −|S| Pr[ X i ′′ ≥ t − 2|S|] = Pr[ X i ′′ = j]

i ∈S /

i ∈S /

j=t−2|S|

n d−1 −|S|

j n d−1 −|S|−j n d−1 − |S| 1 − j |F| − 1 |F| − 1

=

j=t−2|S|

<!-- page 88 -->

We now note that for any positive integers 0 < a < b, any real 0 < p < 1,

b

b b

p j (1 − p) b−j ≤

b−a

2 b p j (1 − p) b−j = 2 b p a

j

j=a

j=a

since

b−a

b−a−k

k

p (1 − p)

≤

k=0

k=0

p k (1 − p) b−a−k ≤ 2 b p a

k=0

b−a b − a

p k (1 − p) b−a−k ,

k

which is the binomial expansion of (p + (1 − p)) b−a = 1

Therefore

t−2|S|

′′ n d−1 −|S| Pr[ X i ≥ t − 2|S|] ≤ 2

i ∈S /

which gives the result.

|F| − 1

In the following lemma again we can obtain further improvements by using the binomial theorem to bound some of the expressions of the proof (e.g. (41) and below)

Lemma 14. [Improvement on Lemma 4 in [ZCF24]] Suppose d min (C d−1 ) ≤ n d−1 − t d−1 . Let t d = 2t d−1 + ℓ d where

|F| λ + 2t d−1 (1 + log( |F|−1 )) + 0.585n d

ℓ d =

then

log(|F| − 1) − 1

Pr[d min (C d ) ≤ n d − t d ] ≤ 2 −λ

Proof. Note that every ĉ ∈ C d is of the form ĉ = (c + c ′ ◦ t d−1 , c − c ′ ◦ t d−1 ) for a unique (c, c ′ ) ∈ C d−1 . We use the shorthand (c, c ′ ) = F (ĉ) Moreover, F (ĉ) ∈ m d (S) for a unique S.

<!-- page 89 -->

Then

Pr[d min (C d ) ≤ n d − t d ] ≤

ĉ∈C d \{0}

=

ĉ∈C d : f (ĉ)∈m d (S)

S⊊[n d−1 ]

|m d (S)| · 2

≤

S⊊[n d−1 ]

t d−1 −1

|F| 2t d−1 −2j

≤

j=0

t d−1 −1

|F| |F| − 1

=

j=0

Pr[w H (ĉ) ≤ n d − t d ]

Pr[w H (ĉ) ≤ n d − t d ]

t d −2|S|

|F| − 1

n d−1 −|S|

t d −2j n d−1 n d−1 −j j |F| − 1

2t d−1 −2j

ℓ d

|F| − 1

n d−1 n d−1 +2t d−1 −3j j

.

where we have used Lemma 13 for the inequality (37)≤(38), Lemma 12 for the inequality (38)≤(39) and t d = 2t d−1 + ℓ d and rearranging terms for the last equality Now (40) can be rearranged as

2t d−1 ·

|F| − 1

|F| |F| − 1

2 n d−1 +2t d−1 ·

ℓ d t d−1 2j X −1 n d−1 · 1 − 2 −3j (41) j |F| j=0

We focus on the sum, upper bounding (1 − |F| ) by 1, which we can write as by reasons that will become clear next. We get

n d−1 −j

t d−1 −1

2j n d−1 X n d−1 1 j 1 − 2 −3j ≤ · 1 n d−1 −j |F| j j=0

n d−1 j

j=0

and we get a binomial sum in the right hand side which equals n d−1 n d−1 +1 =

Coming back to the full expression in (41) (and merging the terms 2 n d−1 and 9 n d−1 the term 8 we have obtained as bound for the sum), we get

|F| |F| − 1

2t d−1

Pr[d min (C d ) ≤ n d − t d ] ≤ 2

·

2t d−1 ·

ℓ d n d−1 ·

|F| − 1

For this to be smaller than 2 −λ we need to set ℓ d as

<!-- page 90 -->

|F| λ + 2t d−1 (1 + log( |F|−1 ) + n d−1 log(9/4)

ℓ d ≥

log( |F|−1 2 )

Using that log(9/4) = 1.1699... ≤ 1.17 and that n d−1 = n d /2, we have that it is enough to set

|F| λ + 2t d−1 (1 + log( |F|−1 )) + 0.585n d

ℓ d =

log(|F| − 1) − 1

The final bound can be now be obtained as in [ZCF24]

Proof (Proof of Theorem 12). Induction. For d = 0 it comes from the assumption that C 0 is an MDS code. In this case d min (C 0 ) = n 0 −k 0 +1 > n 0 −t 0 , so clearly the stated probability is 0.

If d > 0, we assume the property is true for every i ≤ d−1, i.e. Pr[d min (C i ) ≤ n i − t i ] ≤ i · 2 −λ . Let E i be the event “d min (C i ) ≤ n i − t i ”. From the above we are assuming P r[E i ] ≤ i · 2 −λ for i ≤ d − 1. Now note

Pr[E d ] = Pr[E d |E d−1 ] · Pr[E d−1 ] + Pr[E d |¬E d−1 ] · Pr[¬E d−1 ]

≤ Pr[E d−1 ] + Pr[E d |¬E d−1 ]

≤ (d − 1) · 2 −λ + Pr[E d |¬E d−1 ]

But Pr[E d |¬E d−1 ] is precisely the probability analyzed in Lemma 14 and it is at most 2 −λ . Hence Pr[E d ] ≤ d · 2 −λ and we are done. Finally for |F| ≥ 2 11 , log(|F|) − log(|F| − 1) ≤ 0.001, which implies both an |F| ) ≤ 0.001 for the expression in the enumerator and a lower upper bound log( |F|−1 bound log(|F| − 1) − 1 ≥ log |F| − 1.001 for the one in the denominator.

I

Implementation and Evaluation additional details

I.1

Neural Networks

We evaluate the efficiency of our method on a generic neural networks architecture. The aim of our implementation is to demonstrate the feasability of our approach, and not to optimise the machine learning aspect of our solution. For this reason, we do not focus on a particular dataset. We note however, that the neural network architecture that we use could be used, for example, for the income prediction dataset [K + 96] or the Wisconsin breast cancer [WMSS93] one. We focus on a small neural network for a binary classification task, and make use of the following architecture.

Fully connected layer: this layer connects the input nodes to the output nodes. Here, we have 30 inputs for n 0 outputs;

<!-- page 91 -->

Square activation: this is an activation layer; the function f (x) = x 2 is applied to all n 0 input nodes; Fully connected layer: another fully connected layer, connecting n 0 inputs to n 1 outputs; Square activation: this activation layer applies f (x) = x 2 to all n 1 inputs; Fully connected layer: the final fully connected layer, taking n 1 inputs into 2 outputs, corresponding to the two classes.

CKKS constraints We use the following CKKS parameters for all our experiments. We let the ring degree N = 2 13 , L = 2 and log 2 (p i ) = 45, for all the p i in the modulus chain, so that our top modulus is the product of three primes q = q 0 = p 0 p 1 p 2 . Given these parameters, we choose the splitting degree d = 4 to achieve soundness. Both the secret key and the error distributions are Gaussians of width σ = 3.2. The parameters achieve at least 128 bits of security, as estimated by the lattice estimator [APS15].

Additional experimental results

I.2

Table 3 shows the complete measurements for our range proofs. Column “Other” gathers the rest of the prover: the digit decomposition, the partial evaluations ψ̃ η ′ , the counters and the fingerprints of the lookup. The first-layer quotients, which are split into c = 8 chunks, are timed with the measurement for c = 4 at the same ℓ ∗ , i.e., the same number of chunks and the same table.

Table 3: Timing performance of our range proofs: the optimized variant Π̂ range over F p (208-bit p, (σ, m, κ) = (2 , 15, 20)), measured.

Model (n 0 , n 1 ) (128, 64) (64, 16) (32, 16)

Com 3m47s 1m47s 52s

SumCheck 13s 6s 3s

Other 24s 11s 6s

Total 5m54s 2m47s 1m24s

Eval 1m30s 43s 22s

<!-- page 92 -->

Non-zero

(n 0 , n 1 ) Xmult copycon ^ Ṽ 3,det Ṽ 3,copy ⌈log(D)⌉ Ṽ 3,BD Ṽ 3,quot Xmult copycon ^ # copycon ^ variables

(128, 64) 768

24320 12160

(64, 16)

(32, 16)

Table 4: Circuit sizes for the neural network architectures considered. The entries in the columns (n 0 , n 1 ) represent the sizes of the hidden layers. The entries in the columns Xmult and copycon ^ are reported in concrete values. The columns Ṽ 3,BD and Ṽ 3,quot report the number of PC variables needed to represent the wires as multilinear polynomials. Entries in the columns “Non-zero” are reported in log 2 values.