Paper 2025/1943

Circuit-Succinct Algebraic Batch Arguments from Projective Functional Commitments

Abstract

Batch arguments for NP (BARGs) are non-interactive proof systems that allow a prover to convince a verifier that $k$ NP statements $x_1, \ldots, x_k$ are valid relative to some circuit $C$, i.e. there exist witnesses $w_i$ such that $(x_i, w_i)$ satisfy $C$ for all $i$, while the proof size remains sublinear in $k$. Most existing BARG constructions achieve a proof size of $|\pi| = poly(\lambda, |C|, \log k)$ for large or not explicitly specified $poly$ acting on $|C|$, with two exceptions: - Devadas et al. and Paneth and Pass's ''rate-1'' constructions [FOCS'22] achieve $|\pi| = |w| + O(|w|/\lambda) + poly(\lambda, \log k)$ (with matching verification time for Paneth and Pass), but for not explicitly specified $poly$ due to non-black-box use of cryptographic primitives. - Waters and Wu's algebraic (pairing-based) construction [Crypto'22] and follow-up works achieve $|\pi| = O(\lambda \cdot |C|)$. In this work, we give the first algebraic (pairing-based) construction of BARG that achieves proof size and online verifier runtime $O(\lambda \cdot |w|)$. We achieve our result by means of a compiler which builds a BARG generically from a projective chainable functional commitment (PCFC), which supports somewhere extraction, subvector projection, and functional openings. We then construct a PCFC from the standard MDDH assumption in bilinear groups by building on top of the functional commitment for circuits by Wee and Wu [Eurocrypt'24]. Our black-box transformation may be of independent interest for understanding the connection between functional commitments and BARGs and towards obtaining other algebraic constructions of the latter.