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 .