Paper 2025/2285

Laminate: Succinct SIMD-Friendly Verifiable FHE

Zeyu Liu, Yale University

Ben Fisch, Yale University

Eran Tromer, Boston University

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.

Note: Revision Notes (April 10, 2026): Added explicit discussion on special class of payload circuits studied by prior works: "laned circuits", which consist of one or more independent copies of the same arithmetic circuit that can be executed in SIMD with no interaction between slots. Added a Laminate variant tailored to the case of laned circuits. Updated performance estimates (significant improvements with tighter analysis). Added security proofs for our VCoED schemes. Presentation improvements. Revision Note (May 6, 2026): Earlier versions of this preprint contained a soundness bug in the transcript packing compiler, which caused us to report smaller proof sizes than what is actually needed. We describe the bug and a concrete attack exploiting it in Section 7.2.2. This revision corrects the issue by introducing a randomized well-formedness test, at the cost of increasing proof size by $\lambda$ ciphertexts (see Section 7.2.1). Runtime estimates for the server, as well as end-to-end multiplicative depth, remain unchanged.

@misc{cryptoeprint:2025/2285,
      author = {Kabir Peshawaria and Zeyu Liu and Ben Fisch and Eran Tromer},
      title = {Laminate: Succinct {SIMD}-Friendly Verifiable {FHE}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/2285},
      year = {2025},
      url = {https://eprint.iacr.org/2025/2285}
}