Paper 2026/247

Pairing-Based BARG for NP with Constant-Size Proofs and Applications

Abstract

This paper presents a pairing-based non-interactive batch argument (BARG) for NP in the common reference string (CRS) model with constant-size proofs and constant-cost verification. Our construction is fully black-box in its use of the underlying group and achieves a weak form of somewhere extractability under a new $q$-type assumption in composite-order pairing groups. We further show that this extractability guarantee implies somewhere soundness. Prior pairing-based BARGs in this setting suffer from proof size and verification cost proportional to the size of the Boolean circuit computing the NP relation, and our work removes this dependence. Technically, our starting point is the Waters--Wu framework [Asiacrypt'25] and the main idea is to replace the univariate polynomial commitment with a bivariate polynomial commitment together with univariate sumcheck arguments. This allows us to compress both wire and gate checks into a constant number of algebraic identities, leading to constant-size proofs and constant-cost verification. As a demonstration of the resulting somewhere-sound BARG, we show that it simplifies and improves existing generic constructions of NIZKs and rate-1 BARGs. In particular, we obtain: -a generic construction of NIZKs for NP from our somewhere-sound BARG, together with a one-time dual-mode commitment scheme with extraction and a leakage-resilient weak pseudorandom function. The resulting proof size is independent of the circuit size, whereas prior work incurs circuit-size-dependent proof overhead and either requires a local PRG or commits to all internal wires; -a generic construction of rate-1 BARGs from pairing-based assumptions by combining the somewhere sound BARG obtained from our construction with existing rate-1 fully local somewhere-extractable hashing. The resulting proof size is $h+\mathsf{poly}(\lambda,\log\ell)$, whereas prior work either requires proof size $h+o(h)\mathsf{poly}(\lambda,\log\ell)$ or relies on a RAM SNARG with partial-input soundness. Both generic constructions rely on weaker or fewer cryptographic primitives than prior work and the construction of NIZK also avoids the complicated parameter selection in prior work.