Paper 2022/1760
Fully Succinct Batch Arguments for NP from Indistinguishability Obfuscation
Abstract
Non-interactive 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 non-interactive arguments (SNARGs); however, existing constructions of SNARGs either rely on idealized models or strong non-falsifiable assumptions. The one exception is the Sahai-Waters 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 one-way 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)
-
PDF
- 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
- 2024-03-01: last of 2 revisions
- 2022-12-23: 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} }