Welcome to the resource topic for 2022/1760
Title:
Fully Succinct Batch Arguments for NP from Indistinguishability Obfuscation
Authors: Rachit Garg, Kristin Sheridan, Brent Waters, David J. Wu
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.
ePrint: https://eprint.iacr.org/2022/1760
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .