PRISM: Efficient zkSNARKs for RNS-Based Homomorphic Encryption

Homomorphic Encryption (HE) enables computations on encrypted data without decryption, but it does not guarantee the integrity or correctness of the performed operations. To address this limitation, verifiable HE (vHE) has been proposed. However, achieving efficient vHE for RNS-based HE schemes (e.g., BFV/BGV/CKKS) remains challenging: While the Residue Number System (RNS) boosts performance of HE via multi-modulus ciphertext representations, it significantly complicates the cross-field consistency checks in vHE. We observe that existing vHEs for RNS-based HE suffer from at least one of the following limitations: they do not readily extend to the zero-knowledge setting (Atapoor et al., CiC 2024), incur linear proof size & verifier cost (Zhou et al., S&P 2025), or are designed for a modified HE scheme (Cascudo et al., Crypto 2025).

We present $\mathsf{PRISM}$, the first practical zkSNARK for standard RNS-based HEs. Our techniques are threefold: (1) a new cryptographic primitive called Multiple-Field Polynomial Commitment Scheme (MF-PCS) that efficiently prove the cross-field modulo relations, which is the key bottleneck in RNS-based HE verification; (2) a novel Polynomial Interactive Oracle Proof (PIOP) for (inverse) number theoretic transforms with $O(N)$ prover time and $O(\log N)$ verifier time in a model with an offline phase; (3) upgrading MF-PCS and PIOPs to achieve zero-knowledge with small overhead via Vector Oblivious Linear Evaluation (VOLE) correlations. We fully implemented $\mathsf{PRISM}$ and evaluated it against state-of-the-art schemes. Compared to Zhou et al. which has the fastest prover time, $\mathsf{PRISM}$ has $3.5\times$ slower prover time, but up to $7.8\times$ faster verifier time and $7.8\times$ smaller proof size. Compared to Atapoor et al. which has the smallest proof size, $\mathsf{PRISM}$ has $5.5\times$ larger proof size, but roughly $10.1\times$ faster prover time and $2.6\times$ faster verifier time.