1970-01-01

(2026-05) Lasagne; Practical Verifiable Computation over Encrypted Data

[[Xinxuan Zhang]]
[[Ruida Wang]]
[[Qingyun Niu]]
[[Peixin Liu]]
[[Xianhui Lu]]
[[Lutan Zhao]]
[[Rui Hou]]
[[Yi Deng]]

2026-05-01

Abstract

Verifiable Computation on Encrypted Data (VCoED) addresses the computational integrity gap in Fully Homomorphic Encryption (FHE). While recent protocols have made significant strides in making VCoED feasible, server-side proof generation remains computationally intensive, often requiring hours for a modest $2^{20}$ -gate payload circuit (e.g., 2.27 hours for Phalanx, 9.26 hours for Blind Fractal). Moreover, most existing schemes lack support for payload circuits that are homomorphically executed with SIMD operations.

In this work, we present Lasagne, a new efficient VCoED scheme for BGV/BFV-type FHE schemes. Lasagne offers the following:

It supports multiplicative layered payload circuits and allows them to be homomorphically evaluated under SIMD message encoding, which aligns with the requirements of practical FHE deployment.
It achieves efficient prover time while maintaining acceptable communication/verification overhead, and supports flexible parameters choosing to trade off prover time and communication overhead.

For a 16-layer, $2^{20}$ -gate payload circuit, Lasagne generates a 30 MB proof in just 6–12 minutes(single core), achieving an $11\times$ – $23\times$ speedup over Phalanx (2.27 hours, 61.4 MB). When the payload natively supports SIMD execution ( $2^4$ slots), the proving time further reduces to 4–5 minutes (a $27\times$ – $34\times$ speedup). We instantiate Lasagne for a face recognition application built on FHE. Empirical results confirm the validity of our time estimates and the practical viability of the scheme.