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
Hailong Wang, Digital Technologies, Ant Group
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
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
Li Lin, Digital Technologies, Ant Group
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 prime fields creates verifiable FHE challenges. In this work, we construct a packed sumcheck protocol 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 field. For a field $\mathbb{F}_p$ requiring $k$-fold expansion, our sumcheck protocol operates with $(\log k + l)$ variables, where the sumcheck statement consists of $d$ multiplied multilinear polynomial statements. The prover can complete the proof in $O(kd^2 + k^{1.807}d) \cdot 2^l$ modular multiplications and $O(k^2d^2)\cdot 2^l$ modular additions over $\mathbb{F}_p$. We futher propose a proof system for bit-wise bootstrapping by integrating the packed sumcheck protocol with the Brakedown (CRYPTO 2023) and Binius (EUROCRYPT 2025) commitment schemes. Our construction exploits the highly repetitive structure of bit-wise bootstrapping by decomposing the procedure into a sequence of vector operations, enabling the design of an efficient proof protocol through the verification of these vector relations. The resulting system has linear prover time while performing all computations over the base field.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
SNARKssumcheckverifiable FHE.
Contact author(s)
weiyuanju @ iie ac cn
wangkaixuan @ sjtu edu cn
xiangbinwu @ iie ac cn
zhangxinxuan @ iie ac cn
whl383799 @ antgroup com
deng @ iie ac cn
zhuxudong @ iie ac cn
felix ll @ alibaba-inc com
History
2025-05-17: last of 2 revisions
2025-04-22: received
See all versions
Short URL
https://ia.cr/2025/719
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2025/719,
      author = {Yuanju Wei and Kaixuan Wang and Binwu Xiang and Xinxuan Zhang and Hailong Wang and Yi Deng and Xudong Zhu and Li Lin},
      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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.