International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Fully Succinct Batch Arguments for NP from Indistinguishability Obfuscation

Authors:
Rachit Garg , UT Austin
Kristin Sheridan , UT Austin
Brent Waters , UT Austin and NTT Research
David J. Wu , UT Austin
Download:
Search ePrint
Search Google
Presentation: Slides
Conference: TCC 2022
Abstract: Non-interactive batch arguments for NP provide a way to amortize the cost of NP verification across multiple instances. In particular, they allow a prover to convince a verifier of multiple NP statements with communication that scales sublinearly in the number of instances. In this work, we study fully succinct batch arguments for 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 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 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 π on T statements (x1,…,xT) and "update" it to obtain a proof π′ on (x1,…,xT,xT+1). Notably, the update procedure only requires knowledge of a (short) proof for (x1,…,xT) along with a single witness wT+1 for the new instance xT+1. Importantly, the update does not require knowledge of witnesses for x1,…,xT.
BibTeX
@inproceedings{tcc-2022-32623,
  title={Fully Succinct Batch Arguments for NP from Indistinguishability Obfuscation},
  publisher={Springer-Verlag},
  author={Rachit Garg and Kristin Sheridan and Brent Waters and David J. Wu},
  year=2022
}