TY - GEN

T1 - Boosting Batch Arguments and RAM Delegation

AU - Kalai, Yael

AU - Lombardi, Alex

AU - Vaikuntanathan, Vinod

AU - Wichs, Daniel

N1 - 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 -