Paper 2025/719

SNARKs over Small Prime Fields without Extension Field Multiplication

Abstract

Sumcheck-based transparent SNARKs over small prime fields encounter a basic soundness bottleneck. When instantiated over $\mathbb{F}_p$, the round-by-round soundness error is $O(d/p)$, where $d$ is the degree parameter in the sumcheck instance. This is non-negligible for small $p$. A common remedy is to work over an extension field, which departs from native $\mathbb{F}_p$ arithmetic and requires implementing general $\mathbb{F}_{p^k}$ arithmetic, in particular multiplication. A natural alternative is to amplify soundness by parallel repetition. However, naive $k$-parallel repetition does not achieve a proportional $k$-fold increase in round-by-round soundness for multi-round sumcheck. In this work, we propose the \emph{packed sumcheck protocol}, which amplifies round-by-round soundness over $\mathbb{F}_p$ by combining repetition with folding, while avoiding extension field multiplication. The core idea is to couple $k$ independent instances within each round using random matrix challenges from the matrix ring $\mathbb{F}_p^{k \times k}$, so that every folding step mixes all $k$ coordinates. For degree-$d$ claims, we obtain round-by-round soundness error $\bigl(((2k-1)d)/p\bigr)^k$. The prover uses $O((kd^2+k^2d)N)$ base field multiplications and the verifier uses $O(k^2 d\mu)$ base field operations, with communication $O(k d\mu)$ base field elements, where $N=2^\mu$ is the size of the $\mu$-dimensional Boolean hypercube. To compile the packed sumcheck protocol into SNARKs, we introduce \emph{matrix-weighted multilinear extension (MW-MLE) commitments}, capturing the matrix-weighted linear forms induced by packed sumcheck, and instantiate them by adapting Brakedown (CRYPTO~2023) and Basefold (CRYPTO~2024). The resulting components are integrated into the HyperPlonk (EUROCRYPT~2023) framework by replacing its sumcheck and polynomial commitment modules with packed variants, obtaining transparent SNARK instantiations without extension field multiplication in the Random Oracle Model. We further apply our packed techniques to construct a TFHE-friendly SNARK; we evaluate its prover performance for a single bootstrapping, obtaining a prover time of 2.2 seconds.