Paper 2022/1320

Boosting Batch Arguments and RAM Delegation

Yael Tauman Kalai, Microsoft Research, Massachusetts Institute of Technology
Alex Lombardi, Simons Institute, University of California, Berkeley
Vinod Vaikuntanathan, Massachusetts Institute of Technology
Daniel Wichs, Northeastern University, NTT Research
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).

Metadata
Available format(s)
PDF
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
2022-10-05: received
See all versions
Short URL
https://ia.cr/2022/1320
License
Creative Commons Attribution-ShareAlike
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.