Publications

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.