Paper 2026/247
Efficient Pairing-Based Batch Arguments for NP with a Constant-Size Proof
Abstract
Non-interactive Batch arguments (BARGs) for NP relations enable a prover to generate a single succinct proof for multiple NP instances, significantly amortizing verification costs. While recent pairing-based BARGs achieve impressive results, their practical efficiency remains limited by proof sizes and verifier pairing operations that scale linearly with the size of the Boolean circuit computing the NP relation. In this work, we present a novel pairing-based BARG construction that achieves constant proof size and a constant number of pairing operations, independent of both the number of instances and the circuit size. Our approach leverages a bivariate polynomial commitment to compactly encode all wire values across instances, and introduces a new efficient bi-to-uni variate sumcheck protocol, called BuLosum. BuLosum improves upon prior techniques by reducing proving costs to a single multi-scalar multiplication and verification to only three pairings. Using BuLosum, we further design an optimized matrix multiplication protocol that minimizes both proof size and verification overhead. By integrating these components, we obtain the first pairing-based BARG achieving constant-size proofs and constant number of pairing operations.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Preprint.
- Keywords
- Polynomial CommitmentSumcheck SchemeMatrix MultiplicationBatch Arguments
- Contact author(s)
-
52275902014 @ stu ecnu edu cn
kzhang @ shiep edu cn
jqgong @ sei ecnu edu cn
hfqian @ cs ecnu edu cn - History
- 2026-02-16: approved
- 2026-02-13: received
- See all versions
- Short URL
- https://ia.cr/2026/247
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2026/247,
author = {Zhe Jiang and Kai Zhang and Junqing Gong and Haifeng Qian},
title = {Efficient Pairing-Based Batch Arguments for {NP} with a Constant-Size Proof},
howpublished = {Cryptology {ePrint} Archive, Paper 2026/247},
year = {2026},
url = {https://eprint.iacr.org/2026/247}
}
