Welcome to the resource topic for 2025/1943
Title:
Circuit-Succinct Algebraic Batch Arguments from Projective Functional Commitments
Authors: David Balbás, Dario Fiore, Russell W. F. Lai
Abstract:Batch arguments for NP (BARGs) are non-interactive proof systems that allow a prover to convince a verifier that k NP statements x_1, \ldots, x_k are valid relative to some circuit C, i.e. there exist witnesses w_i such that (x_i, w_i) satisfy C for all i, while the proof size remains sublinear in k. Most existing BARG constructions achieve a proof size of |\pi| = poly(\lambda, |C|, \log k) for large or not explicitly specified poly acting on |C|, with two exceptions:
- Devadas et al. and Paneth and Pass’s ‘‘rate-1’’ constructions [FOCS’22] achieve |\pi| = |w| + O(|w|/\lambda) + poly(\lambda, \log k) (with matching verification time for Paneth and Pass), but for not explicitly specified poly due to non-black-box use of cryptographic primitives.
- Waters and Wu’s algebraic (pairing-based) construction [Crypto’22] and follow-up works achieve |\pi| = O(\lambda \cdot |C|).
In this work, we give the first algebraic (pairing-based) construction of BARG that achieves proof size and online verifier runtime O(\lambda \cdot |w|). We achieve our result by means of a compiler which builds a BARG generically from a projective chainable functional commitment (PCFC), which supports somewhere extraction, subvector projection, and functional openings. We then construct a PCFC from the standard MDDH assumption in bilinear groups by building on top of the functional commitment for circuits by Wee and Wu [Eurocrypt’24]. Our black-box transformation may be of independent interest for understanding the connection between functional commitments and BARGs and towards obtaining other algebraic constructions of the latter.
ePrint: https://eprint.iacr.org/2025/1943
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 .