Packed Sumcheck over Fields of Small Characteristic with Application to Verifiable FHE

Yuanju Wei; Kaixuan Wang; Binwu Xiang; Xinxuan Zhang; Yi Deng; Hailong Wang; Xudong Zhu

Paper 2025/719

Packed Sumcheck over Fields of Small Characteristic with Application to Verifiable FHE

Yuanju Wei, State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China, School of Cyber Security, University of Chinese Academy of Sciences, Beijing, China

Kaixuan Wang, Shanghai Jiao Tong University

Binwu Xiang, State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China, School of Cyber Security, University of Chinese Academy of Sciences, Beijing, China

Xinxuan Zhang, State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China, School of Cyber Security, University of Chinese Academy of Sciences, Beijing, China

Yi Deng, State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China, School of Cyber Security, University of Chinese Academy of Sciences, Beijing, China

Hailong Wang, Digital Technologies, Ant Group

Xudong Zhu, State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China, School of Cyber Security, University of Chinese Academy of Sciences, Beijing, China

Abstract

Verifiable computation over encrypted data is gaining increasing attention, and using SNARKs to provide proofs for FHE operations has emerged as a promising approach. However, the mismatch between FHE's typically small prime fields and SNARKs' larger field requirements creates verifiable FHE challenges. In this work, we construct a packed sumcheck algorithm specifically designed for small fields. This approach leverages folding and repetition techniques to maintain security without field expansion, with all operations performed on the base domain. For a domain requiring -fold expansion, our sumcheck protocol operates with variables, where each sumcheck statement consists of multiplied multilinear polynomial statements. The prover can complete the computation in modular multiplications over . By exploiting the highly repetitive computational structure in bit-wise FHE bootstrapping operations, we decompose the process into a series of vector operations. Building upon the packed sumcheck technique along with the Brakedown (CRYPTO 2023) and Binius (EUROCRYPT 2025) commitment schemes, we construct an efficient proof system for these vector operations, ultimately yielding a proof system for bit-wise FHE. Our system achieves linear prover time while performing all computations on the base field, resulting in significant improvements in prover efficiency.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Preprint.
Keywords: SNARKs sumcheck verifiable FHE.
Contact author(s): weiyuanju @ iie ac cn
wangkaixuan @ sjtu edu cn
xiangbinwu @ iie ac cn
zhangxinxuan @ iie ac cn
deng @ iie ac cn
whl383799 @ antgroup com
zhuxudong @ iie ac cn
History: 2025-04-23: approved; 2025-04-22: received; See all versions
Short URL: https://ia.cr/2025/719
License: CC BY

BibTeX

@misc{cryptoeprint:2025/719,
      author = {Yuanju Wei and Kaixuan Wang and Binwu Xiang and Xinxuan Zhang and Yi Deng and Hailong Wang and Xudong Zhu},
      title = {Packed Sumcheck over Fields of Small Characteristic with Application to Verifiable {FHE}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/719},
      year = {2025},
      url = {https://eprint.iacr.org/2025/719}
}