Batch, Pack, and Prove: More Efficient Verifiable Computation for CKKS
summary
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.
In short
The paper introduces a PIOP $\Pi$CKKS protocol for RCKKS homomorphic encryption by combining three techniques: BatchFold for shorter polynomial commitments, packing for efficient range proofs, and improved arithmetization. This results in significantly smaller proof sizes and faster verification times compared to previous methods like Basefold.
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 used across episodes
This episode discusses
The paper
Batch, Pack, and Prove: More Efficient Verifiable Computation for CKKS · Read on arXiv
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.
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.
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.
More episodes
- 2608.27496-ROPE: Routed Origin Policy Enforcement against Indirect Prompt Injection
- Daily Summary for 2026-11-19
- 2607.07085-Is Randomness Necessary for Adaptive Data Analysis?
- The day in conversation for 2026-11-19
- Daily Summary for 2026-11-19
- 2609.10601-Threshold Choice, Not Sample Size, Bounds Trustless Verification of Nondeterministic Compound AI Workflows
- 2610.38786-Adversarial Process Disturbances at a Deployable Alarm Budget: Detector Evaluation on a Simulator and a Real Plant
- 2511.08660-Binary and Multiclass Cyberattack Classification on GeNIS Dataset
- 2604.27302-Static Attribution of Android Residential Proxy Malware Using Graph Kernels
- Daily Summary for 2026-11-18