[Resource Topic] 2022/1320: Boosting Batch Arguments and RAM Delegation

Welcome to the resource topic for 2022/1320

Boosting Batch Arguments and RAM Delegation

Authors: Yael Tauman Kalai, Alex Lombardi, Vinod Vaikuntanathan, Daniel Wichs


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-\epsilon}, 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 \mathsf{poly} (m)\cdot \mathsf{poly} \log k, which is the gold standard for succinctness of $\mathsf{BARG}s. By prior work, such \mathsf{BARG}s imply the existence of \mathsf{SNARG}$s for deterministic time T computation with optimal succinctness \mathsf{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 $\mathsf{BARG}s and \mathsf{SNARG}s with polylogarithmic succinctness based on either bilinear maps or a combination of the \mathsf{DDH} and \mathsf{QR}$ assumptions.

Along the way, we prove an equivalence between $\mathsf{BARG}s and a new notion of \mathsf{SNARG}s for (deterministic) \mathsf{RAM} computations that we call ``flexible \mathsf{RAM} \mathsf{SNARG}s with partial input soundness." This is the first demonstration that \mathsf{SNARG}s for deterministic computation (of any kind) imply \mathsf{BARG}s. Our \mathsf{RAM} \mathsf{SNARG} notion is of independent interest and has already been used in a recent work on constructing rate-1 \mathsf{BARG}$s (Devadas et. al. FOCS 2022).

ePrint: https://eprint.iacr.org/2022/1320

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .