Welcome to the resource topic for 2022/1236
Title:
Rate-1 Non-Interactive Arguments for Batch-NP and Applications
Authors: 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:
- 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.
ePrint: https://eprint.iacr.org/2022/1236
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .