TY - GEN

T1 - Boosting Batch Arguments and RAM Delegation

AU - Kalai, Yael

AU - Lombardi, Alex

AU - Vaikuntanathan, Vinod

AU - Wichs, Daniel

N1 - Funding Information:
This research was conducted in part while AL was at MIT, where he was supported by a Charles M. Vest Grand Challenges Fellowship, an NDSEG Fellowship, and grants of VV. VV is supported in part by DARPA under Agreement No. HR00112020023, a grant from the MIT-IBM Watson AI, a grant from Analog Devices and a Microsoft Trustworthy AI grant. Any opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the United States Government or DARPA.
Publisher Copyright:
© 2023 Owner/Author.

PY - 2023/6/2

Y1 - 2023/6/2

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

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

KW - Batch Arguments

KW - Delegation of Computation

KW - RAM Delegation

UR - http://www.scopus.com/inward/record.url?scp=85163055430&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85163055430&partnerID=8YFLogxK

U2 - 10.1145/3564246.3585200

DO - 10.1145/3564246.3585200

M3 - Conference contribution

AN - SCOPUS:85163055430

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 1545

EP - 1552

BT - STOC 2023 - Proceedings of the 55th Annual ACM Symposium on Theory of Computing

A2 - Saha, Barna

A2 - Servedio, Rocco A.

PB - Association for Computing Machinery

T2 - 55th Annual ACM Symposium on Theory of Computing, STOC 2023

Y2 - 20 June 2023 through 23 June 2023

ER -