[Resource Topic] 2025/1323: Pairing-Based Batch Arguments for NP with a Linear-Size CRS

Welcome to the resource topic for 2025/1323

Title:
Pairing-Based Batch Arguments for NP with a Linear-Size CRS

Authors: Binyi Chen, Noel Elias, David J. Wu

Abstract:

Non-interactive batch arguments (BARGs) for NP allow a prover to prove \ell NP statements with a proof whose size scales sublinearly with \ell. In this work, we construct a pairing-based BARG where the size of the common reference string (CRS) scales linearly with the number of instances and the prover’s computational overhead is quasi-linear in the number of instances. Our construction is fully black box in the use of the group. Security relies on a q-type assumption in composite-order pairing groups.

The best black-box pairing-based BARG prior to this work has a nearly-linear size CRS (i.e., a CRS of size \ell^{1 + o(1)}) and the prover overhead is quadratic in the number of instances. All previous pairing-based BARGs with a sublinear-size CRS relied on some type of recursive composition and correspondingly, non-black-box use of the group. The main technical insight underlying our construction is to substitute the vector commitment in previous pairing-based BARGs with a polynomial commitment. This yields a scheme that does not rely on cross terms in the common reference string. In previous black-box pairing-based schemes, the super-linear-size CRS and quadratic prover complexity was due to the need for cross terms.

ePrint: https://eprint.iacr.org/2025/1323

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .