Paper 2026/2878

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

Ignacio Cascudo, IMDEA Software Institute
Anamaria Costache, École Polytechnique
Daniele Cozzo, IMDEA Software Institute
Dario Fiore, IMDEA Software Institute
Antonio Guimarães, IMDEA Software Institute
Eduardo Soria-Vazquez, Technology Innovation Institute
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 = \mathbb{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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A major revision of an IACR publication in ASIACRYPT 2026
Keywords
Verifiable ComputationZero-knowledge proofsFHEvfheverifiable homomorphic encryption
Contact author(s)
ignacio cascudo @ imdea org
costache @ lix polytechnique fr
daniele cozzo @ imdea org
dario fiore @ imdea org
antonio guimaraes @ imdea org
eduardo soria-vazquez @ tii ae
History
2026-11-16: approved
2026-11-12: received
See all versions
Short URL
https://ia.cr/2026/2878
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2026/2878,
      author = {Ignacio Cascudo and Anamaria Costache and Daniele Cozzo and Dario Fiore and Antonio Guimarães and Eduardo Soria-Vazquez},
      title = {Batch, Pack, and Prove: More Efficient Verifiable Computation for {CKKS}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/2878},
      year = {2026},
      url = {https://eprint.iacr.org/2026/2878}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.