Paper 2022/1760
Fully Succinct Batch Arguments for NP from Indistinguishability Obfuscation
Abstract
Noninteractive batch arguments for $\mathsf{NP}$ provide a way to amortize the cost of $\mathsf{NP}$ verification across multiple instances. In particular, they allow a prover to convince a verifier of multiple $\mathsf{NP}$ statements with communication that scales sublinearly in the number of instances. In this work, we study fully succinct batch arguments for $\mathsf{NP}$ in the common reference string (CRS) model where the length of the proof scales not only sublinearly in the number of instances $T$, but also sublinearly with the size of the $\mathsf{NP}$ relation. Batch arguments with these properties are special cases of succinct noninteractive arguments (SNARGs); however, existing constructions of SNARGs either rely on idealized models or strong nonfalsifiable assumptions. The one exception is the SahaiWaters SNARG based on indistinguishability obfuscation. However, when applied to the setting of batch arguments, we must impose an a priori bound on the number of instances. Moreover, the size of the common reference string scales linearly with the number of instances. In this work, we give a direct construction of a fully succinct batch argument for $\mathsf{NP}$ that supports an unbounded number of statements from indistinguishability obfuscation and oneway functions. Then, by additionally relying on a somewhere statistically binding (SSB) hash function, we show how to extend our construction to obtain a fully succinct and updatable batch argument. In the updatable setting, a prover can take a proof $\pi$ on $T$ statements $(x_1, \ldots, x_T)$ and "update" it to obtain a proof $\pi'$ on $(x_1, \ldots, x_T, x_{T + 1})$. Notably, the update procedure only requires knowledge of a (short) proof for $(x_1, \ldots, x_T)$ along with a single witness $w_{T + 1}$ for the new instance $x_{T + 1}$. Importantly, the update does not require knowledge of witnesses for $x_1, \ldots, x_T$.
Metadata
 Available format(s)
 Category
 Cryptographic protocols
 Publication info
 A major revision of an IACR publication in TCC 2022
 Keywords
 non interactive Batch Argumentssuccinct arguments
 Contact author(s)

rachg96 @ cs utexas edu
kristin @ cs utexas edu
bwaters @ cs utexas edu
dwu4 @ cs utexas edu  History
 20240301: last of 2 revisions
 20221223: received
 See all versions
 Short URL
 https://ia.cr/2022/1760
 License

CC BY
BibTeX
@misc{cryptoeprint:2022/1760, author = {Rachit Garg and Kristin Sheridan and Brent Waters and David J. Wu}, title = {Fully Succinct Batch Arguments for {NP} from Indistinguishability Obfuscation}, howpublished = {Cryptology {ePrint} Archive, Paper 2022/1760}, year = {2022}, url = {https://eprint.iacr.org/2022/1760} }