Boosting Batch Arguments and RAM Delegation

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 )· k 1−є , 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 , log k ), which is the gold standard for succinctness of BARG s. By prior work, such BARG s imply the existence of SNARG s for deterministic time T computation with succinctness poly (log T ). 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 BARG s and SNARG s 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 BARG s and a new notion of SNARG s for (deterministic) RAM computations that we call “ flexible RAM SNARG s with partial input soundness .” This is the first demonstration that SNARG s for deterministic computation (of any kind) imply BARG s. Our RAM SNARG notion is of independent interest and has already been used in a recent work on constructing rate-1 BARG s (Devadas et. ‍al. FOCS 2022).

Authors

• Yael Tauman Kalai
• Alex Lombardi
• Vinod Vaikuntanathan
• Daniel Wichs

Keywords

• Batch Arguments
• Delegation of Computation
• RAM Delegation