Paper 2022/1320

Boosting Batch Arguments and RAM Delegation

Abstract

We show how to generically improve the succinctness of non-interactive publicly verifiable batch argument ($\mathsf{BARG}$) systems. In particular, we show (under a mild additional assumption) how to convert a $\mathsf{BARG}$ that generates proofs of length $\mathsf{poly}(m)\cdot 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 $$, which is the gold standard for succinctness of $$s. By prior work, such $$s imply the existence of $$s for deterministic time $$ computation with optimal succinctness $$. 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 $$s and $$s with polylogarithmic succinctness based on either bilinear maps or a combination of the $$ and $$ assumptions. Along the way, we prove an equivalence between $$s and a new notion of $$s for (deterministic) $$ computations that we call ``flexible $$ $$s with partial input soundness." This is the first demonstration that $$s for deterministic computation (of any kind) imply $$s. Our $$ $$ notion is of independent interest and has already been used in a recent work on constructing rate-1 $$s (Devadas et. al. FOCS 2022).