Paper 2022/1236

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

Lalita Devadas, Massachusetts Institute of Technology
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: - A multi-hop BARG scheme for $\mathsf{NP}$. - A multi-hop aggregate signature scheme (in the standard model). - 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)$ 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
Keywords
delegation batch argument
Contact author(s)
lali @ mit edu
History
2022-09-19: approved
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},
      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.