Rate-1 Non-Interactive Arguments for Batch-NP and Applications

ePrint Report: Rate-1 Non-Interactive Arguments for Batch-NP and Applications

Lalita Devadas, Rishab Goyal, Yael Kalai, Vinod Vaikuntanathan

We present a rate-$1$ construction of a publicly verifiable non-interactive argument system for batch-$\mathsf{NP}$ (also called a BARG), under the LWE assumption. Namely, a proof corresponding to a batch of $k$ NP statements each with an $m$-bit witness, has size $m + \mathsf{poly}(\lambda,\log k)$.


In contrast, prior work either relied on non-standard knowledge assumptions, or produced proofs of size $m \cdot \mathsf{poly}(\lambda,\log k)$ …

applications batch eprint report non rate