Paper 2025/719

Packed Sumcheck over Fields of Small Characteristic

Abstract

The sumcheck protocol is a fundamental primitive in the construction of probabilistic proof systems. Its soundness relies on the Schwartz--Zippel lemma and is therefore typically instantiated over large fields. However, proving small field computations such as FHE via sumcheck over large fields incurs the substantial overhead of large field arithmetic. So there is strong interest in sumcheck over small fields. In this work, we present \emph{packed sumcheck}, a new protocol for small prime fields that combines repetition with folding to preserve round-by-round soundness while keeping all computations in the base field $\mathbb{F}_p$. Under the assumption $p^k = O(2^\lambda)$, where $\lambda$ is the security parameter, proving a sumcheck instance consisting of the product of $d$ multilinear polynomial over $(\log k+l)$ variables (with $N=2^l$ and instance size $kN$) requires $O((kd^2+k^2d)N)$ multiplications and $O(k^2 d^2 N)$ additions over $\mathbb{F}_p$. While the standard approach requires $O(k^3d^2N)$ operations over $\mathbb{F}_p$. For concrete performance, we instantiate our protocol over the Babybear field and obtain at least a $2.78\times$ speedup over the state of the art. As a direct application, we design a TFHE-friendly SNARK. We express TFHE bootstrapping (J. Cryptol 2020) as a collection of vector relations, commit them using a variant of Brakedown (CRYPTO 2023) and Binius (EUROCRYPT 2025), and verify them via our packed sumcheck. The experiments demonstrate a proof generation time of 2.02s for a single bootstrapping, surpassing the best previously reported results.