Paper 2022/1236
Rate-1 Non-Interactive Arguments for Batch-NP and Applications
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
-
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}, url = {https://eprint.iacr.org/2022/1236} }