Paper 2022/336

Batch Arguments for NP and More from Standard Bilinear Group Assumptions

Brent Waters, The University of Texas at Austin, NTT Research
David J. Wu, The University of Texas at Austin

Non-interactive batch arguments for NP provide a way to amortize the cost of NP verification across multiple instances. They enable a prover to convince a verifier of multiple NP statements with communication much smaller than the total witness length and verification time much smaller than individually checking each instance. In this work, we give the first construction of a non-interactive batch argument for NP from standard assumptions on groups with bilinear maps (specifically, from either the subgroup decision assumption in composite-order groups or from the $k$-Lin assumption in prime-order groups for any $k \ge 1$). Previously, batch arguments for NP were only known from LWE, or a combination of multiple assumptions, or from non-standard/non-falsifiable assumptions. Moreover, our work introduces a new direct approach for batch verification and avoids heavy tools like correlation-intractable hash functions or probabilistically-checkable proofs common to previous approaches. As corollaries to our main construction, we obtain the first publicly-verifiable non-interactive delegation scheme for RAM programs (i.e., a succinct non-interactive argument (SNARG) for P) with a CRS of sublinear size (in the running time of the RAM program), as well as the first aggregate signature scheme (supporting bounded aggregation) from standard assumptions on bilinear maps.

Available format(s)
Cryptographic protocols
Publication info
A major revision of an IACR publication in CRYPTO 2022
BARG non-interactive batch arguments delegation succinct arguments
Contact author(s)
bwaters @ cs utexas edu
dwu4 @ cs utexas edu
2022-06-11: revised
2022-03-14: received
See all versions
Short URL
Creative Commons Attribution


      author = {Brent Waters and David J. Wu},
      title = {Batch Arguments for {NP} and More from Standard Bilinear Group Assumptions},
      howpublished = {Cryptology ePrint Archive, Paper 2022/336},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.