### Batch Arguments for NP and More from Standard Bilinear Group Assumptions

##### Abstract

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)
Category
Cryptographic protocols
Publication info
A major revision of an IACR publication in CRYPTO 2022
Keywords
BARG non-interactive batch arguments delegation succinct arguments
Contact author(s)
bwaters @ cs utexas edu
dwu4 @ cs utexas edu
History
2022-06-11: revised
See all versions
Short URL
https://ia.cr/2022/336

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.