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- construction of a publicly verifiable non-interactive argument system for batch- (also called a BARG), under the LWE assumption. Namely, a proof corresponding to a batch of NP statements each with an -bit witness, has size . In contrast, prior work either relied on non-standard knowledge assumptions, or produced proofs of size (Choudhuri, Jain, and Jin, STOC 2021, following Kalai, Paneth, and Yang 2019). We show how to use our rate- BARG scheme to obtain the following results, all under the LWE assumption in the standard model: - A multi-hop BARG scheme for . - A multi-hop aggregate signature scheme. - An incrementally verifiable computation (IVC) scheme for arbitrary -time deterministic computations with proof size . 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 were known under a bilinear map assumption, and with proofs of size 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},
      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.