Paper 2022/336

Batch Arguments for NP and More from Standard Bilinear Group Assumptions

Brent Waters and David J. Wu

Abstract

A non-interactive batch argument for NP provides 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 also obtain the first publicly-verifiable non-interactive delegation scheme for RAM programs 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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. Minor revision.
Keywords
BARGnon-interactive batch argumentsdelegationsuccinct arguments
Contact author(s)
bwaters @ cs utexas edu
dwu4 @ cs utexas edu
History
2022-03-14: received
Short URL
https://ia.cr/2022/336
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/336,
      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{https://eprint.iacr.org/2022/336}},
      url = {https://eprint.iacr.org/2022/336}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.