Paper 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 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 Computation over Encrypted Data (VCoED) with verification faster than local computation remains a challenge. We introduce $\mathsf{Laminate}$, a family of VCoED protocols for adding integrity to computations delegated using BGV/BFV-style FHE. Our approach combines the blind interactive proof framework with the GKR proof system, which avoids computing commitments to intermediate computation states under FHE. Our client-efficient variant employs novel transcript packing and folding techniques that reduce proof size to $O(\log^2 n + N)$ words (suppressing security parameters) for bounded-depth size-$n$ circuits, where $N$ is the BGV/BFV ring dimension. Unlike prior FHE-over-SNARK schemes, $\mathsf{Laminate}$ preserves the SIMD parallelism of FHE for both payload circuit evaluation and proof generation; eliminates the need for witness reductions; is field-agnostic; and adds only constant multiplicative depth on top of payload evaluation while performing $\widetilde{O}(n_{\mathsf{FHE}})$ FHE operations, where $n_{\mathsf{FHE}}$ is the number of payload FHE operations. We give an end-to-end concrete integrity analysis, implement the complete protocol, and provide a reproducible methodology for measuring server overhead and per-request client computation. We benchmark $\mathsf{Laminate}$ on payload circuits with $n=2^{34}$ scalar gates. One scheme variant has an overhead of $21$--$33\times$ compared to FHE evaluation without integrity, with proofs of $52$--$54\,\mathrm{MB}$. Another variant reduces overhead to $10$--$14\times$, with larger proofs. For both, per-request client computation is much faster than local evaluation, demonstrating concrete outsourced computation with privacy and integrity, a key distinction from prior VCoED work.

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. Revision Note (October 21, 2026): This revision adds a C++ implementation of Laminate and replaces microbenchmark-based performance estimates with measurements of server time, proof size, and per-request client time. We also give an end-to-end concrete integrity analysis covering GKR, polynomial commitments, transcript packing, and Fiat--Shamir.