Paper 2025/1323
Pairing-Based Batch Arguments for NP with a Linear-Size CRS
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.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Preprint.
- Keywords
- BARGnon-interactive batch argumentspairings
- Contact author(s)
-
binyi @ cs stanford edu
nelias @ utexas edu
dwu4 @ cs utexas edu - History
- 2025-07-22: approved
- 2025-07-19: received
- See all versions
- Short URL
- https://ia.cr/2025/1323
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2025/1323,
author = {Binyi Chen and Noel Elias and David J. Wu},
title = {Pairing-Based Batch Arguments for {NP} with a Linear-Size {CRS}},
howpublished = {Cryptology {ePrint} Archive, Paper 2025/1323},
year = {2025},
url = {https://eprint.iacr.org/2025/1323}
}
