FHE-SNARK vs. SNARK-FHE: From Analysis to Practical Verifiable Computation

Xinxuan Zhang; Ruida Wang; Zeyu Liu; Binwu Xiang; Yi Deng; Xianhui Lu

Paper 2025/302

FHE-SNARK vs. SNARK-FHE: From Analysis to Practical Verifiable Computation

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

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

Zeyu Liu, Yale University

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

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

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

Abstract

Verifiable Computation over encrypted data (VC) faces a critical dilemma between two competing paradigms: SNARK-FHE (applying SNARKs to prove FHE operations) and FHE-SNARK (homomorphically evaluating SNARK proofs). There are two interesting questions remain open to solving such a dilemma: 1) Are they identical in terms of security? 2) How practically efficient can we get? This work answers these questions through the following results: 1) We establish a formal security analysis between VC and secure two-party computation (2PC). We investigate VC with server inputs and show the following: a) VC with server input has an exact 1-bit security loss compared to 2PC; b) SNARK-FHE aligns with 2PC while FHE-SNARK naturally falls in the VC category; c) Existing FHE-SNARK works is vulnerable in the VC with server input setting, for which we formalize a input-dependent attack. 2) We design an FHE-friendly SNARK that is: a) 3× lower multiplicative depth than FRI-based SNARKs; b) Compatible with FHE SIMD operations. Based on this novel SNARK, we construct an FHE-SNARK scheme that has: a) Stronger security: resistant against input-dependent attack; b) 8× speedup: 3.6-hour proof generation for -gate circuits on a single core CPU (vs. 29 hours in the state-of-the-art); c) Practical verification: 65.3 MB proofs with 2.7 seconds verification (single core).

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Preprint.
Keywords: FHE SNARK Verifiable Computation
Contact author(s): zhangxinxuan @ iie ac cn
wangruida @ iie ac cn
zeyu liu @ yale edu
xiangbinwu @ iie ac cn
deng @ iie ac cn
luxianhui @ iie ac cn
History: 2025-02-21: approved; 2025-02-20: received; See all versions
Short URL: https://ia.cr/2025/302
License: CC BY

BibTeX

@misc{cryptoeprint:2025/302,
      author = {Xinxuan Zhang and Ruida Wang and Zeyu Liu and Binwu Xiang and Yi Deng and Xianhui Lu},
      title = {{FHE}-{SNARK} vs. {SNARK}-{FHE}: From Analysis to Practical Verifiable Computation},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/302},
      year = {2025},
      url = {https://eprint.iacr.org/2025/302}
}