### 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-\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).

Available format(s)
Category
Foundations
Publication info
Preprint.
Keywords
batch argument systems RAM delegation
Contact author(s)
yael @ microsoft com
alexlombardi @ alum mit edu
vinodv @ mit edu
wichs @ ccs neu edu
History
2022-10-05: revised
See all versions
Short URL
https://ia.cr/2022/1320

CC BY-SA

BibTeX

@misc{cryptoeprint:2022/1320,
author = {Yael Tauman Kalai and Alex Lombardi and Vinod Vaikuntanathan and Daniel Wichs},
title = {Boosting Batch Arguments and RAM Delegation},
howpublished = {Cryptology ePrint Archive, Paper 2022/1320},
year = {2022},
note = {\url{https://eprint.iacr.org/2022/1320}},
url = {https://eprint.iacr.org/2022/1320}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.