Paper 2026/003
Batch Arguments with Optimal Communication
, CISPA Helmholtz Center for Information Security, Bocconi University, Tel Aviv UniversityAbstract
Batch arguments (BARGs) are non-interactive arguments for conjunctions of NP statements, with proof size that is sublinear in the number of statements. Several previous works studied the communication complexity of BARGs, focusing both on the CRS size and on the additive overhead of the proof, defined as the difference between the proof size and the size $m$ of a single NP witness: - Devadas et al.~[FOCS 22] constructed BARGs with additive overhead that is independent of $m$, however, their CRS size is polynomial in $m$. - Paneth and Pass [FOCS 22] constructed BARGs where the CRS size is independent of $m$, but with higher additive overhead $m^{1-\epsilon}$. Under the hardness of LWE, we construct BARGs where both the CRS size the additive overhead of the proof are independent of $m$. Such BARGs can be recursively composed an unbounded polynomial number of times without losing succinctness. Along the way, we also considerably simplify the construction of fully local somewhere extractable hash functions used in the construction of Devadas et al.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Preprint.
- Contact author(s)
-
doettling @ cispa de
giulio malavolta @ unibocconi it
omerpa @ tauex tau ac il - History
- 2026-01-03: approved
- 2026-01-01: received
- See all versions
- Short URL
- https://ia.cr/2026/003
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2026/003,
author = {Nico Döttling and Giulio Malavolta and Omer Paneth},
title = {Batch Arguments with Optimal Communication},
howpublished = {Cryptology {ePrint} Archive, Paper 2026/003},
year = {2026},
url = {https://eprint.iacr.org/2026/003}
}
