Batch, Pack, and Prove: More Efficient Verifiable Computation for CKKS
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Security Radio. Generated commentary on the latest security and cryptography papers.
Nadia: I'm Nadia.
Elias: And I'm Elias, here with Priya.
Nadia: We're looking at the paper: "Batch, Pack, and Prove".
Elias: Here's the gist of the paper. The paper addresses bottlenecks in verifiable computation for CKKS homomorphic encryption by introducing several new techniques, combining them into a PIOP pi CKKS protocol for RCKKS.
Nadia: The primary contributions are: 1.
Elias: BatchFold: A novel polynomial commitment scheme for R q that supports batched evaluations and yields shorter proofs, reducing proof size from O(sqrt n) to O(squared n) and improving proving time compared to prior methods like Basefold.
Paper summary: Nadia: So we’re looking at this paper, "Batch, Pack, and Prove: More Efficient Verifiable Computation for CKKS." It tackles the problem of making verifiable computation practical for CKKS homomorphic encryption.
Elias: Right. Basically, they propose a new protocol called a PIOP CKKS specifically for RCKKS. The main idea is to combine several techniques to prove both arithmetic circuits and range checks over that ring Rq = ZqY/(Y N + one), and then tie it all together to prove computations on CKKS ciphertexts <ref:2611.16922#pg1,ring Rq = Zq Y /(Y N + 1), and>.
Priya: So, what’s the big hurdle they’re trying to clear? I mean, the abstract mentions challenges like proof size and an O of N overhead in range proofs.
Nadia: Exactly. The paper claims they've addressed those scalability challenges by introducing a few new things to make it much more efficient than previous work, like Basefold.
Elias: They have three main contributions that really drive this whole PIOP CKKS thing. First, they have something called BatchFold, which is a novel polynomial commitment scheme for Rq that supports batched evaluations and makes the proofs shorter.
Priya: Shorter proofs sound good, but how much shorter are we talking about compared to what’s out there?
Elias: They claim it reduces proof size from O of N square root to O of log squared N, which is a big jump over previous methods like Basefold. This also improves the proving time.
Nadia: And then they introduce this new algebraic technique called packing and unpacking in PIOPs. This lets them get rid of committing to massive polynomials, which removes that O of N overhead associated with range proofs.
Priya: So, if you can avoid committing to those huge polynomials, does that make the verification part much faster?
Elias: It does. This enables SparsePack, which is an efficient protocol for proving evaluations of sparse and circuit dependent polynomials. That means they can operate efficiently using sparse representations of unpacked polynomials.
Nadia: And on top of that, they have improved arithmetization and preprocessing for CKKS circuits. They designed closed-form polynomials for wiring predicates related to CKKS homomorphic multiplication, which lets the verifier compute those predicates much more efficiently.
Priya: So, we’ve got a better way to handle commitments, a better way to handle range checks through packing, and a smarter way to arithmetize the circuits themselves. That sounds like they're trying to attack this from several angles at once.
Elias: Exactly. The overall framework builds the PIOP CKKS for RCKKS by integrating all these components—range checks over packed polynomials using PIOPs with Packing, and arithmetic circuits proven via improved arithmetization through SparsePack.
Nadia: The results they show are pretty compelling when you look at the performance gains. They’ve shown proof sizes that are several orders of magnitude smaller than prior solutions like Spark.
Priya: That is a huge difference in scale, especially when dealing with complex computations on CKKS ciphertexts. What about the execution time? Does it actually run faster for the prover?
Paper summary: Elias: They show a factor of two point eight improvement in execution time over Basefold for evaluation proofs <ref:2611.16922#pg2>. And they’ve got verification times that are asymptotically polylogarithmic in circuit size, which is much better than the square root verification complexity seen in prior work like CCC plus twenty-five.
Nadia: The paper also points out some technical advantages for the prover. They allow the prover to tolerate those extra costs of quasilinear proving time because verification becomes significantly faster, especially since many committed polynomials are a factor of N smaller than in that previous work.
Priya: So, if I’m just listening to this, what does this mean practically? Does this make verifiable computation something we can actually use for real-world things?
Elias: It means the combined approach achieves proof sizes several orders of magnitude smaller and faster than previous methods when tested on generic neural network architectures. The protocol achieves verification times that scale well with the circuit size.
Nadia: The paper also points out a limitation, which is kind of important for us as researchers. They mention that this solution does not require commitments at run time because all commitments depend only on the circuit and are precomputed, but they don't solve every single problem in HE yet.
Priya: So, to wrap up this summary of "Batch, Pack, and Prove," we have a new protocol that combines polynomial commitment schemes with packing techniques and better circuit representations to handle verifiable computation for CKKS.
Elias: The authors are Ignacio Cascudo, Anamaria Costache, Daniele Cozzo, Dario Fiore, Antonio Guimarães, and Eduardo Soria-Vazquez. This work is about improving the efficiency of proving computations on CKKS ciphertexts by tackling proof size and range check overhead through new tools like BatchFold and Packing in PIOPs.
Nadia: It seems like they’ve moved the needle significantly on how we can actually make verifiable computation practical for schemes like CKKS.
Priya: So, if you listen to this, the main point is that we can now achieve much smaller proofs and faster verification times for these kinds of computations compared to what was previously possible with methods like Basefold.
Elias: The core technical story here is how combining packing for range checks with improved arithmetization leads to a SparsePack protocol that proves evaluations of sparse polynomials efficiently.
Nadia: This whole PIOP CKKS structure is what lets the system handle both the arithmetic part and the range checks in a unified, efficient way.
Priya: It’s about moving away from those massive commitments and toward something more sparse and manageable when you are proving things on encrypted data.
Elias: The implications are that we can tackle larger circuits with less overhead in terms of proof size and time compared to the previous state of the art.
Nadia: So, for anyone listening, this paper shows a concrete way to reduce the computational cost associated with verifying computations in homomorphic encryption schemes like CKKS.
Conclusion: Nadia: So we're wrapping up our look at this paper, "Batch, Pack, and Prove: More Efficient Verifiable Computation for CKKS."
Elias: It's about taking homomorphic encryption proofs and making them way smaller and faster by using some new tricks.
Priya: It focuses on solving the problem of those big proof sizes that used to make verifiable computation impractical for things like neural networks.
Nadia: Exactly. They’re combining a new commitment scheme called BatchFold with an idea called packing to handle range checks over polynomials, and they've also improved how they arithmetize the CKKS circuits themselves.
Elias: The main result is that this combined approach cuts proof size down several orders of magnitude compared to older methods like Basefold. We’re talking about a factor of nine point five improvement in proof size for evaluation proofs alone.
Priya: That kind of reduction in data size is huge when you're dealing with encrypted data and trying to send it somewhere else to be verified. What does that actually mean for the privacy aspect?
Nadia: It means the verification process itself becomes much more feasible, even for very large circuits. The authors show verification times are now polylogarithmic in circuit size, which is way better than square root scaling we saw before.
Elias: And they've made things precomputed too, so you don't have to do any commitments at run time when you're doing the proving part. That removes another layer of overhead for the prover.
Priya: So it’s not just smaller proofs; it’s a more streamlined process that keeps verification from becoming a bottleneck for privacy-preserving computations.
Nadia: Right. The authors, Ignacio Cascudo and others, have built this PIOP CKKS protocol to integrate all these parts—the range checks over packed polynomials and the arithmetic circuits proven by SparsePack—into one unified system.
Elias: It’s a lot of moving pieces put together to handle both the arithmetic structure and those necessary range checks in a way that scales well.
Priya: It really shows how combining different techniques, like packing for sparsity and better circuit representations, can lead to substantial practical gains in this area.
Nadia: We've seen some big wins with generic neural network architectures using this method. But the authors do mention that they are focused on RCKKS specifically for now and there are still areas where they’re looking to improve things further.
Elias: That’s fair. They aren't claiming perfection yet, but they've shown a very solid path forward for making these computations practical instead of just theoretical examples.
Ignacio Cascudo, Anamaria Costache, Daniele Cozzo, Dario Fiore, Antonio Guímaraes, Eduardo Soria-Vazquez
IMDEA Software Institute Madrid, Spain. · École Polytechnique Paris, France. · Technology Innovation Institute Abu Dhabi, UAE.
cs.CR
Submitted: 2026-11-12
Updated: 2026-11-12
Comments: Full version of a paper accepted at ASIACRYPT 2026. 92 pages
Code: https://github.com/vfhe/Batch-Pack-and-Prove
License: http://creativecommons.org/licenses/by/4.0/
Importance score: 93/100
The gist: The paper addresses bottlenecks in verifiable computation for CKKS homomorphic encryption by introducing several new techniques, combining them into a PIOP pi CKKS protocol for RCKKS.
Key concepts
- BatchFold
- This is a new polynomial commitment scheme designed specifically for RCKKS. It allows the system to handle batched evaluations of polynomials efficiently, which dramatically reduces the size of the required proofs. It improves proof size from $O(\sqrt{n})$ down to $O(\log^2 n)$ and speeds up the proving process.
- Packing and Unpacking in PIOPs
- Packing is a new algebraic method used within Polynomial IOPs (PIOPs) to avoid committing to very large polynomials. This technique eliminates the $O(N)$ overhead that usually comes with range proofs, allowing protocols like SparsePack to work efficiently with sparse representations of polynomials.
- Improved Arithmetization
- This involves a new way of representing CKKS circuits. It creates closed-form polynomials for wiring predicates related to homomorphic multiplication. This makes it much easier and faster for the verifier to check these predicates, reducing the overall size and complexity of encoding polynomials.
- PIOP $\Pi$CKKS Protocol
- This is the complete framework that integrates all new components. It uses PIOPs with Packing for range checks on packed polynomials and SparsePack for proving arithmetic circuits using improved arithmetization. The goal is to create a highly efficient verifiable computation system for RCKKS.
Terminology
Summary
The paper addresses bottlenecks in verifiable computation for CKKS homomorphic encryption by introducing several new techniques, combining them into a PIOP pi CKKS protocol for RCKKS. p. 0 In this paper we present new techniques that remove all these bottlenecks. First, we provide a more efficient arithmetization of CKKS computations.Where the paper says it
-
BatchFold: A novel polynomial commitment scheme for R q that supports batched evaluations and yields shorter proofs, reducing proof size from O(sqrt n) to O(squared n) and improving proving time compared to prior methods like Basefold.
-
Packing and Unpacking in PIOPs: A new algebraic technique called packing is introduced to eliminate the need to commit to massive polynomials, thereby removing the O(N) overhead associated with range proofs. This enables PIOPs (Polynomial IOPs) to operate efficiently using sparse representations of unpacked polynomials, leading to the construction of SparsePack, an efficient protocol for proving evaluations of sparse, circuit-dependent polynomials. p. 0
Where the paper says it
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.
-
Improved Arithmetization and Preprocessing: A new arithmetization for CKKS circuits is presented that enhances prior work by designing closed-form polynomials for wiring predicates related to CKKS homomorphic multiplication. This allows the verifier to compute these predicates efficiently, substantially reducing the number and size of encoding polynomials. p. 6
Where the paper says it
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).
The overall framework constructs a PIOP pi CKKS for RCKKS by integrating these components: range checks over packed polynomials are handled using PIOPs with Packing, and arithmetic circuits are proven using improved arithmetization via SparsePack. p. 1 14
4 Our PIOP for Range Checks over Packed Polynomials . 15
5 Improved Arithmetization and PIOP ΠAC for CKKS .Where the paper says it
Key results demonstrate significant performance gains:
-
Proof Size Reduction: The combined approach achieves proof sizes several orders of magnitude smaller than prior solutions like Spark. Specifically, the new scheme shows a factor of 9. p. 5
5 improvement in proof size compared to Basefold for evaluation proofs, and a factor of 2. p. 6Where the paper says it
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.
8 improvement in execution time over Basefold for evaluation proofs (Table 2). p. 6Where the paper says it
5) improvement in execution time (resp. proof size) compared to Basefold.
Where the paper says it
5) improvement in execution time (resp. proof size) compared to Basefold.
-
Efficiency Gains: The protocol achieves verification times that are asymptotically polylogarithmic in the circuit size, surpassing the square-root verification complexity of prior work like [CCC+25]. The optimized PIOP pi* range protocol exhibits improved efficiency, with prover time O(kappa times 2* + 2b/c) and verifier time O(* + b/c + kappa times 2*-m).
-
Technical Advantages: The new techniques allow the prover to tolerate the extra costs of quasilinear proving time in exchange for significantly faster verification, as many committed polynomials are a factor O(N) smaller than in [CCC+25]. Furthermore, the solution does not require commitments at run time, as all commitments depend only on the circuit and are precomputed. p. 5
Where the paper says it
ciency improvements on generic neural networks, demonstrating the feasibility of verifiable HE for MLaaS applications. To reduce the O( √ n) proof size of Brakedown commitments used in [CCC+25], we build on BaseFold [ZCF24], which achieves O log2 n proofs and O(n log n) proving time.
Experiments on generic neural network architectures confirm that this combined approach yields proofs several orders of magnitude smaller and faster than previous methods. p. 0 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.Where the paper says it
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
BatchFold improves performance over BaseFold by reducing proof size by up to a factor of 9.5 times while achieving a performance improvement of up to 2.8 times for evaluation proofs on Rq with N = 213 and 3 RNS components.
-
Packing and SparsePack reduce proof sizes by more than an order of magnitude compared to Spark, yielding a proof size reduction from approximately 6.5 GiB down to about 163 MiB for neural network applications.
-
The improved arithmetization of CKKS allows the verifier to compute closed form equations for wiring predicates efficiently and minimizes the number and size of polynomials encoding the circuit structure that need to be proven.
-
The SparsePack PIOP is specialized to prove the evaluation of sparse polynomials, achieving a proof size reduction by more than an order of magnitude compared to standard polynomial commitments in cubic circuit size.
-
The overall protocol can achieve polylogarithmic verification time in the circuit size, which suggests that verification costs can be amortized and be faster than trivial solutions for sufficiently large computations.
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.
Related papers
- From Strategy Search to Policy Learning: MCTS-Guided Adversarial Co-Evolution for LLM Safety Alignment
- Privacy Leakage from Recurrent State in LLM Inference
- Incrementally Verifiable Oracle Aided Computation
- Privilege and confidentiality in generative AI workflows
- BadMoE: Backdooring Mixture-of-Experts LLMs via Routing-Aware Triggers and Task-Underutilized Experts
- CoVault: Secure, Scalable Analytics of Personal Data