**Accumulators in (and Beyond) Generic Groups: Non-Trivial Batch Verification Requires Interaction**

*Gili Schul-Ganz and Gil Segev*

**Abstract: **We prove a tight lower bound on the number of group operations required for batch verification by any generic-group accumulator that stores a less-than-trivial amount of information. Specifically, we show that $\Omega(t \cdot (\lambda / \log \lambda))$ group operations are required for the batch verification of any subset of $t \geq 1$ elements, where $\lambda \in \mathbb{N}$ is the security parameter, thus ruling out non-trivial batch verification in the standard non-interactive manner.

Our lower bound applies already to the most basic form of accumulators (i.e., static accumulators that support membership proofs), and holds both for known-order (and even multilinear) groups and for unknown-order groups, where it matches the asymptotic performance of the known bilinear and RSA accumulators, respectively. In addition, it complements the techniques underlying the generic-group accumulators of Boneh, B{\"{u}}nz and Fisch (CRYPTO '19) and Thakur (ePrint '19) by justifying their application of the Fiat-Shamir heuristic for transforming their interactive batch-verification protocols into non-interactive procedures.

Moreover, motivated by a fundamental challenge introduced by Aggarwal and Maurer (EUROCRYPT '09), we propose an extension of the generic-group model that enables us to capture a bounded amount of arbitrary non-generic information (e.g., least-significant bits or Jacobi symbols that are hard to compute generically but are easy to compute non-generically). We prove our lower bound within this extended model, which may be of independent interest for strengthening the implications of impossibility results in idealized models.

**Category / Keywords: **foundations / Accumulators, batch verification

**Original Publication**** (with major differences): **IACR-TCC-2020

**Date: **received 14 Sep 2020

**Contact author: **gili schul at cs huji ac il,segev@cs huji ac il

**Available format(s): **PDF | BibTeX Citation

**Version: **20200915:112906 (All versions of this report)

**Short URL: **ia.cr/2020/1106

[ Cryptology ePrint archive ]