CS Paper Radar

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

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

cs.CR ·submitted 2026-11-12 15:09 UTC · v1
publishedhot direction

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.

Comment
Full version of a paper accepted at ASIACRYPT 2026. 92 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Constant-Rate Certified Deletion

cs.CR quant-ph ·2026-10-02 ·Kai-Min Chung, Tzu-Hsiang Huang, Wei-Hsiang Hung, Shota Yamada
top venue similarity 0.66
Abstract

We present a unified framework for upgrading a broad class of cryptographic primitives to support constant-rate certified deletion. Previous constructions require a linear number of qubits per encrypted bit of certified-deletable plaintext. In contrast, we obtain the first constant-rate constructions in the plain model that achieve certified deletion while preserving everlasting security. Our approach applies to a wide range of "all-or-nothing"-type primitives based on BB84-style encodings, including commitment schemes, public-key encryption, attribute-based encryption, and fully homomorphic encryption. Beyond this class, we also obtain constant-rate certified deletion for primitives built from subspace coset states, such as blind delegation, secure software leasing, functional encryption, and differing-inputs iO, and CCA-PKE. Importantly, our framework does not introduce any additional assumptions beyond those required by the underlying certified deletion primitives. Finally, under the hardness of SIS, we show that public verifiability can be incorporated into BB84- and coset-based certified deletion. In combination with our constant-rate constructions, this yields publicly verifiable certified deletion schemes with constant rate.

0.38

BenX: Resource-Sharing Permutations for Computational Integrity

cs.CR ·2026-09-25 ·Luca Campa, Thomas De Cnudde, Al Kindi, Arnab Roy, Fabian Schmid +2 more
similarity 0.65
Abstract

Cryptographic hash functions over integers modulo a prime play a decisive role in the efficiency and security of proof systems for computational integrity. Early designs focused on compact arithmetic circuits and efficient software execution, primarily targeting general-purpose CPUs rather than hardware accelerators. This work focuses on enabling efficient resource sharing and hardware acceleration alongside efficient software execution. We propose BenX, a permutation-based hash function designed for hardware acceleration, fast CPU execution, and low circuit complexity in proof systems. To construct the underlying permutation, we turn the Benes network into an invertible function over $\mathbb{F}_p^2$ using a Dickson polynomial. Its structure yields a permutation particularly suited to hardware resource sharing and acceleration. Fully pipelined on FPGA, BenX matches the throughput of Poseidon2, with 1.36x and 2.15x lower latency for Goldilocks and BabyBear, respectively. Although larger as a standalone core, it makes more effective use of shared hardware: in our dual-mode architecture, where the NTT and hash share field multipliers, BenX keeps 100% of them busy, compared with 6.25-20.3% for the partial rounds of Poseidon and Poseidon2. In software, BenX outperforms Poseidon in all tested 31- and 64-bit configurations, but is slower than Poseidon2, except for the 16-element BabyBear instance. In zero-knowledge proofs, BenX proves Goldilocks permutations 6-10x faster than Monolith. Its compact arithmetization uses about 36% fewer trace cells than Poseidon and Poseidon2 over BabyBear, while its fast variant requires 1.3-2.6x the prover time of Poseidon2.

0.22

zk-DEAP: A Zero-Knowledge Decentralized Encrypted Aggregation Protocol

cs.CR ·2026-11-04 ·Jude Ramanan, Georgiana Haldeman, Noah Apthorpe
similarity 0.65
Abstract · 19 pages, 5 figures, 5 tables

Secure aggregation in domains such as federated learning, Internet of Things, and voting requires operating on private inputs while preserving confidentiality, verifying that each input satisfies constraints, and avoiding trusted parties. Existing protocols achieve at most two of these requirements. We present zk-DEAP, a protocol combining lifted ElGamal homomorphic encryption, FROST threshold cryptography, and zero-knowledge proofs (Bulletproofs, zk-SNARKs, or zk-STARKs) for fully decentralized, verifiable, privacy-preserving aggregation. Our core technical contribution is a cryptographic binding mechanism preventing substitution attacks, where a valid proof for one input is paired with a ciphertext encrypting a different, malicious value. For Bulletproofs, we bind via ciphertext-derived randomness modification. For zk-SNARKs/zk-STARKs, to bind across algebraic structures (a well-known challenge in practical cryptography), we introduce a novel blinded arithmetic hash commitment with an embedded Schnorr constraint. These binding techniques force the ZKP's private witness to equal the encrypted value, ensuring any circuit-verified constraint applies to the ciphertext. We implement three production-ready, defense-in-depth variants in Rust and evaluate across 5-500 participants. Compared to unverified aggregation, zk-DEAP adds modest overhead while providing cryptographic guarantees against input manipulation that statistical defenses cannot match.

0.28

When and Where Faults Matter: A Study of Transient Errors in CKKS Multiplication

cs.AR cs.CR ·2026-08-11 ·Vattana Chan, Matías Mazzanti, Karthik Swaminathan, Augusto Vega, Esteban Mocskos +1 more
similarity 0.64
Abstract · 3 pages, 2 figures

Homomorphic Encryption (HE) is a privacy-preserving encryption paradigm that enables computation directly on encrypted data without requiring decryption. In this paper, we study errors in fully homomorphic encryption (FHE) computations, with a particular focus on server-side homomorphic multiplication in the unoptimized CKKS (Cheon--Kim--Kim--Song) scheme. We show that both the timing and the location of errors in the ciphertext components \(c_0\) and \(c_1\) have a significant impact on the correctness of the final FHE output.

0.03

FASTAR: FRI Accelerator for Scalable Transparent ARguments of Knowledge

cs.CR ·2026-09-22 ·Tengkai Gong, Xiaolin Xu
published similarity 0.64
Abstract · 9 pages, 2 figures, 4 tables; ICCAD 2026

Zero-Knowledge Proofs (ZKPs) enable a prover to cryptographically convince a verifier of the validity of a statement without revealing any underlying secrets, forming a foundational primitive for verifiable computation. The ZKP landscape is undergoing a fundamental shift from classic zk-SNARKs such as Groth16, which rely on trusted setup and are vulnerable to quantum adversaries, toward transparent, post-quantum constructions such as zk-STARK. These systems achieve post-quantum security by relying solely on collision-resistant hash functions, however, at the cost of substantial computational overhead. In particular, the Fast Reed--Solomon Interactive Oracle Proof of Proximity (FRI) protocol dominates prover complexity, generating massive data volumes, repeated Merkle-tree commitments, and irregular memory access patterns that limit performance and energy efficiency on general-purpose processors. To address these challenges, this work proposes FASTAR, a novel FPGA-based accelerator for the FRI protocol. Unlike accelerators that pursue fixed high-performance kernels on expensive ASIC process nodes, FASTAR adopts a constraint-driven design methodology. Our framework is implemented with High-Level Synthesis (HLS) and composed of fully parameterizable building blocks for the major stages of FRI, including polynomial evaluation, recursive split-and-fold, and Merkle-tree construction. From user-provided board specifications, FASTAR automatically generates hardware implementations tailored to the resource and memory constraints of the target FPGA, enabling deployment across a wide range of platforms without manual redesign.

0.31

A Little Derandomization Goes a Long Way: Unconditional Circuit Lower Bounds using Low-Degree PIT

cs.CC ·2026-11-05 ·Nikolai Chukhin, Karthik Gajulapalli, Alexander Golovnev, Ivan Mihajlin
theory similarity 0.64
Abstract

We prove unconditionally that either NE contains a language requiring Boolean circuits of size at least $2^n/(2n)$, or $VP^0_{\mathbb{Z}}\ne VNP^0_{\mathbb{Z}}$, a constant-free version of Valiant's conjecture over the integers. The Boolean alternative implies that $NP\not\subseteq SIZE[n^k]$ for every constant $k\ge1$. Our proof gives a fine-grained variant of the connection between Polynomial Identity Testing (PIT) and circuit lower bounds established by Kabanets and Impagliazzo (2004). We show that the specific identity tests required by this argument can be performed over the integers without a derandomization assumption. Over a fixed finite field $\mathbb{F}$, we first give a deterministic $O(st^{d-1})$-time algorithm for PIT on size-$s$ circuits computing degree-$d$ polynomials in $t$ variables. We further show that, for any fixed $d\ge2$ and $\varepsilon>0$, improving this running time by a factor of $t^{\varepsilon}$, even nondeterministically, implies either the same Boolean lower bound or an arithmetic circuit lower bound of $t^{1+\varepsilon/2}$ for a polynomial family from $VNP_{\mathbb{F}}$. If nondeterministic PIT instead runs in time $s^{o(d)}t^{(1-\varepsilon)d}$ for infinitely many degrees $d$, then the arithmetic lower bound strengthens to $VP_{\mathbb{F}}\ne VNP_{\mathbb{F}}$. Over the integers, we give a deterministic PIT algorithm for syntactically set-multilinear circuits running in time $s^{O(1)}t^{5d/6}$, which yields the unconditional result above. Combining the Kabanets-Impagliazzo argument with range avoidance, we show that an NP algorithm for PIT over $\mathbb{Z}$ gives a purely arithmetic win-win: either $VP_{\mathbb{Z}}\ne VNP_{\mathbb{Z}}$, or constant-degree polynomials of maximum circuit complexity can be constructed in FNP.

0.23

A Lightweight Fault-Detection Scheme for Barrett Modular Multiplication Using Multiple Conditional Reduction Paths

cs.CR ·2026-08-11 ·Rourab Paul, Paresh Baidya, Krishnendu Guha, Amlan Chakrabarti
similarity 0.63
Abstract

Polynomial multiplication is the most resource-, time-, and energy-critical operation in lattice-based Post-Quantum Cryptography (PQC) and Fully Homomorphic Encryption (FHE) schemes. Lattice-based PQC schemes such as Kyber and Dilithium have already been standardized, while lattice- based FHE schemes such as BGV, BFV, and CKKS are widely recognized as leading candidate in FHE area. Barrett Modular Multiplication (BMM) for polynomial multiplication is widely adopted in PQC and FHE hardware accelerators due to its hardware friendly nature and efficient modular reduction capabilities. However, Side-Channel Attacks (SCAs) and Hardware Trojans may introduce intentional faults, while aging and various other factors can cause unintentional faults. These faults may target the BM M unit, one of the most critical components of PQC and FHE infrastructures, potentially leading to information leakage and compromising system security. In this paper, we employ a Statistical Reduction Monitoring (SRM) method to protect the BM M unit against such adversarial conditions. The proposed approach incurs minimal hardware overhead while providing efficient detection of both random and bur

0.04

Delegating Computation with Approximate Arithmetic: Interactive Proofs for Wizards

cs.CR ·2026-11-08 ·Aritra Das, Debayan Gupta, Arup Mondal, Mihir More
similarity 0.62
Abstract

We study interactive proofs for arithmetic circuits over the complex numbers $\mathbb{C}$ in which both the prover and the verifier compute approximately (unlike muggles, wizards can use magic, i.e., floating-point numbers). The goal is to prove that a claimed output $y$ is close to the exact output $C(x)$: for thresholds $0<Δ_0<Δ$, the honest prover is accepted whenever $|y-C(x)|\leΔ_0$, and every prover is rejected with high probability whenever $|y-C(x)|>Δ$. Existing proof systems for real-valued data verify rounded finite-field computations. Bitan et al.~[EUROCRYPT~2026] gave an approximate sum-check protocol. We extend the protocol of Goldwasser, Kalai, and Rothblum (GKR) [STOC~2008] to public-coin interactive proofs for logspace-uniform layered circuits over $\mathbb{C}$ of size $S$, depth $L$, and $n$ inputs, under public bounds on gate values and wiring coefficients. At constant soundness error, the verifier runs in time $(n+1)\mathrm{poly}(L,\log S,b)$, the communication is $\mathrm{poly}(L,\log S,b)$, and the prover runs in time $\mathrm{poly}(S,b)$, where $b$ is the bit precision. To the best of our knowledge, these are the first doubly efficient interactive proofs in which both parties compute approximately. GKR reduces two claims about a layer to one on a random line, which leaves the unit circle, where our error bounds hold. We instead label gates by complex roots of unity and combine the two claims with a random root of unity as coefficient. We choose the error thresholds backward from the input layer, so that a large output error survives the verifier's rounding at every step. The honest prover needs only $O(S \log S)$ complex operations. We also obtain zero-knowledge proofs from one-way functions, one-round arguments from private information retrieval, and interactive PCPs whose proof length is polynomial in the witness length.

0.36