Rate-1 Non-Interactive Arguments for Batch-NP and Applications
Lalita Devadas, Rishab Goyal, Yael Tauman Kalai, Vinod Vaikuntanathan
Abstract
We present a rate-1 construction of a publicly verifiable non-interactive argument system for batch-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+poly(\lambda, log k)$.In contrast, prior work either relied on non-standard knowledge assumptions, or produced proofs of size m. poly $(\lambda, \log k)$ (Choudhuri, Jain, and Jin, STOC 2021, following Kalai, Paneth, and Yang 2019).We show how to use our rate-l BARG scheme to obtain the following results, all under the LWE assumption:•A multi-hop BARG scheme for 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 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 poly $(\lambda, T^{\epsilon})$ were known under a bilinear map assumption, and with proofs of size poly $(\lambda, log T)$ under non-standard knowledge assumptions or in the random oracle model.