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 $$ in the common reference string (CRS) model where the length of the proof scales not only sublinearly in the number of instances $$, but also sublinearly with the size of the $$ 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 $$ 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 $$ on $$ statements $$ and "update" it to obtain a proof $$ on $$. Notably, the update procedure only requires knowledge of a (short) proof for $$ along with a single witness $$ for the new instance $$. Importantly, the update does not require knowledge of witnesses for $$.