Phalanx: An FHE-Friendly SNARK for Verifiable Computation on Encrypted Data

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

Paper 2025/302

Phalanx: An FHE-Friendly SNARK for Verifiable Computation on Encrypted Data

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, East China Normal University

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

Ben Fisch, Yale University

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 (VCoed) has two popular paradigms: SNARK-FHE (applying SNARKs to prove FHE operations) and FHE-SNARK (homomorphically evaluating SNARK proofs). For the existing works, FHE-SNARK has a much better efficiency compared to SNARK-FHE. In this work, we follow the line of FHE-SNARK and further improve its efficiency by designing Phalanx—an FHE-friendly SNARK that is: a) 3× lower multiplicative depth than FRI-based SNARKs; and b) Compatible with FHE SIMD operations. Based on Phalanx, we construct an FHE-SNARK scheme that has: a) $7.3×\sim 24.4×$ speedup: 2.27-hour proof generation for $2^{20}$-gate circuits on a single core CPU and 0.68-hour when the input ciphertexts are in iNTT form (vs. 16.57 hours in the state-of-the-art); and b) Practical verification: 61.4 MB proofs with 2.8 seconds verification (single core).

Note: Full Version

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Published elsewhere. Major revision. ACM CCS 2025
DOI: 10.1145/3719027.3765226
Keywords: FHE SNARK Verifiable Computation on Encrypted Data
Contact author(s): zhangxinxuan @ iie ac cn
wangruida @ iie ac cn
zeyu liu @ yale edu
bwxiang @ sc ecnu edu cn
deng @ iie ac cn
ben fisch @ yale edu
luxianhui @ iie ac cn
History: 2025-10-19: last of 4 revisions; 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 Ben Fisch and Xianhui Lu},
      title = {Phalanx: An {FHE}-Friendly {SNARK} for Verifiable Computation on Encrypted Data},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/302},
      year = {2025},
      doi = {10.1145/3719027.3765226},
      url = {https://eprint.iacr.org/2025/302}
}