Publications

Fully Succinct Batch Arguments for NP from Indistinguishability Obfuscation

Rachit Garg, Kristin Sheridan, Brent Waters, and David J. Wu

Theory of Cryptography Conference (TCC), 2022

Resources

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 \).

BibTeX
@inproceedings{GSWW22,
  author    = {Rachit Garg and Kristin Sheridan and Brent Waters and David J. Wu},
  title     = {Fully Succinct Batch Arguments for {NP} from Indistinguishability Obfuscation},
  booktitle = {{TCC}},
  year      = {2022}
}