Welcome to the resource topic for 2022/1320
Title:
Boosting Batch Arguments and RAM Delegation
Authors: Yael Tauman Kalai, Alex Lombardi, Vinod Vaikuntanathan, Daniel Wichs
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-\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 .