Paper 2026/857

Lasagne: Practical Verifiable Computation over Encrypted Data

, State Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, CAS, School of Cyber Security, University of Chinese Academy of Sciences

Ruida Wang, State Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, CAS, School of Cyber Security, University of Chinese Academy of Sciences

Qingyun Niu, State Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, CAS, School of Cyber Security, University of Chinese Academy of Sciences

Peixin Liu, School of Microelectronics, Southern University of Science and Technology

Xianhui Lu, State Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, CAS, School of Cyber Security, University of Chinese Academy of Sciences

Lutan Zhao, State Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, CAS

Rui Hou, State Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, CAS

Yi Deng, Xidian University

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: 1. 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. 2. 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.

@misc{cryptoeprint:2026/857,
      author = {Xinxuan Zhang and Ruida Wang and Qingyun Niu and Peixin Liu and Xianhui Lu and Lutan Zhao and Rui Hou and Yi Deng},
      title = {Lasagne: Practical Verifiable Computation over Encrypted Data},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/857},
      year = {2026},
      url = {https://eprint.iacr.org/2026/857}
}