Paper 2021/807
Non-Interactive Batch Arguments for NP from Standard Assumptions
Arka Rai Choudhuri, Abhishek Jain, and Zhengzhong Jin
Abstract
We study the problem of designing *non-interactive batch arguments* for $\mathsf{NP}$. Such an argument system allows an efficient prover to prove multiple $\mathsf{NP}$ statements, with size smaller than the combined witness length. We provide the first construction of such an argument system for $\mathsf{NP}$ in the common reference string model based on standard cryptographic assumptions. Prior works either require non-standard assumptions (or the random oracle model) or can only support private verification. At the heart of our result is a new *dual mode* interactive batch argument system for $\mathsf{NP}$. We show how to apply the correlation-intractability framework for Fiat-Shamir -- that has primarily been applied to proof systems -- to such interactive arguments.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- A minor revision of an IACR publication in CRYPTO 2021
- Keywords
- Batch argumentsFiat-Shamir Transformation
- Contact author(s)
-
achoud @ cs jhu edu
abhishek @ cs jhu edu
zjin12 @ jhu edu - History
- 2021-06-16: received
- Short URL
- https://ia.cr/2021/807
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2021/807,
author = {Arka Rai Choudhuri and Abhishek Jain and Zhengzhong Jin},
title = {Non-Interactive Batch Arguments for NP from Standard Assumptions},
howpublished = {Cryptology ePrint Archive, Paper 2021/807},
year = {2021},
note = {\url{https://eprint.iacr.org/2021/807}},
url = {https://eprint.iacr.org/2021/807}
}
