Paper 2025/719
Packed Sumcheck over Fields of Small Characteristic with Application to Verifiable FHE
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
-
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} }