Paper 2025/2285 Original: eprint.iacr.org/2025/2285 ↗

Laminate: Succinct SIMD-Friendly Verifiable FHE

Abstract

In outsourcing computation to untrusted servers, one can cryptographically ensure privacy using Fully Homomorphic Encryption (FHE) or ensure integrity using Verifiable Computation (VC) such as SNARK proofs. While each is practical for some applications in isolation, efficiently composing FHE and VC into Verifiable Computing on Encrypted Data (VCoED) remains an open problem. We introduce $\mathsf{Laminate}$, the first practical method for adding integrity to BGV-style FHE, thereby achieving VCoED. Our approach combines the blind interactive proof framework with a tailored variant of the GKR proof system that avoids committing to intermediate computation states. We further introduce variants employing transcript packing and folding techniques. The resulting encrypted proofs are concretely succinct: $13$MB, compared to $1$TB in prior work, to evaluate a batch of $B=2^{14}$ instances of size $n=2^{20}$ and depth $d=32$. Asymptotically, the proof size and verifier work is $O(d \log (Bn) + N)$, compared to $\Omega(BN\log n)$ in prior work (for ring dimension $N$). Unlike prior schemes, $\mathsf{Laminate}$ utilizes the full SIMD capabilities of FHE for both the payload circuit evaluation and proof generation; adds only constant multiplicative depth on top of payload evaluation while performing $\tilde{O}(n)$ FHE operations; eliminates the need for witness reduction; and is field-agnostic. The resulting cost of adding integrity to FHE, compared to assuming honest evaluation, is ${\sim}5\times$ to ${\sim}67\times$ overhead (for circuits of size $2^{20}$), which is $>2300\times$ faster than the state-of-the-art.