Boosting Batch Arguments and RAM Delegation

Yael Kalai, Alex Lombardi, Vinod Vaikuntanathan, Daniel Wichs

Research output: Chapter in Book/Report/Conference proceedingConference contribution

9 Scopus citations

Abstract

We show how to generically improve the succinctness of non-interactive publicly verifiable batch argument (BARG) systems. In particular, we show (under a mild additional assumption) how to convert a BARG that generates proofs of length poly (m)· k1-", where m is the length of a single instance and k is the number of instances being batched, into one that generates proofs of length poly (m, logk), which is the gold standard for succinctness of BARGs. By prior work, such BARGs imply the existence of SNARGs for deterministic time T computation with succinctness poly(logT). Our result reduces the long-standing challenge of building publicly-verifiable delegation schemes to a much easier problem: building a batch argument system that beats the trivial construction. It also immediately implies new constructions of BARGs and SNARGs with polylogarithmic succinctness based on either bilinear maps or a combination of the DDH and QR assumptions. Along the way, we prove an equivalence between BARGs and a new notion of SNARGs for (deterministic) RAM computations that we call "flexible RAM SNARGs with partial input soundness."This is the first demonstration that SNARGs for deterministic computation (of any kind) imply BARGs. Our RAM SNARG notion is of independent interest and has already been used in a recent work on constructing rate-1 BARGs (Devadas et.al. FOCS 2022).

Original languageEnglish (US)
Title of host publicationSTOC 2023 - Proceedings of the 55th Annual ACM Symposium on Theory of Computing
EditorsBarna Saha, Rocco A. Servedio
PublisherAssociation for Computing Machinery
Pages1545-1552
Number of pages8
ISBN (Electronic)9781450399135
DOIs
StatePublished - Jun 2 2023
Externally publishedYes
Event55th Annual ACM Symposium on Theory of Computing, STOC 2023 - Orlando, United States
Duration: Jun 20 2023Jun 23 2023

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Conference

Conference55th Annual ACM Symposium on Theory of Computing, STOC 2023
Country/TerritoryUnited States
CityOrlando
Period6/20/236/23/23

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Batch Arguments
  • Delegation of Computation
  • RAM Delegation

Fingerprint

Dive into the research topics of 'Boosting Batch Arguments and RAM Delegation'. Together they form a unique fingerprint.

Cite this