Paper 2022/1236

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

Lalita Devadas
Rishab Goyal
Yael Kalai
Vinod Vaikuntanathan
Abstract

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)$ (Choudhuri, Jain, and Jin, STOC 2021, following Kalai, Paneth, and Yang 2019). We show how to use our rate-$1$ BARG scheme to obtain the following results, all under the LWE assumption in the standard model: - A multi-hop BARG scheme for $\mathsf{NP}$. - A multi-hop aggregate signature scheme. - An incrementally verifiable computation (IVC) scheme for arbitrary $T$-time deterministic computations with proof size $\mathsf{poly}(\lambda,\log T)$. Prior to this work, multi-hop BARGs were only known under non-standard knowledge assumptions or in the random oracle model; aggregate signatures were only known under indistinguishability obfuscation (and RSA) or in the random oracle model; IVC schemes with proofs of size $\mathsf{poly}(\lambda,T^{\epsilon})$ were known under a bilinear map assumption, and with proofs of size $\mathsf{poly}(\lambda,\log T)$ were only known under non-standard knowledge assumptions or in the random oracle model.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. IEEE Symposium on Foundations of Computer Science
DOI
10.1109/FOCS54457.2022.00103
Keywords
delegationbatch argument
Contact author(s)
lali @ mit edu
History
2023-04-07: last of 3 revisions
2022-09-18: received
See all versions
Short URL
https://ia.cr/2022/1236
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/1236,
      author = {Lalita Devadas and Rishab Goyal and Yael Kalai and Vinod Vaikuntanathan},
      title = {Rate-1 Non-Interactive Arguments for Batch-NP and Applications},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1236},
      year = {2022},
      doi = {10.1109/FOCS54457.2022.00103},
      note = {\url{https://eprint.iacr.org/2022/1236}},
      url = {https://eprint.iacr.org/2022/1236}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.