Non-Interactive Batch Arguments for NP from Standard Assumptions

Arka Rai Choudhuri; Abhishek Jain; Zhengzhong Jin

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 $NP$ . Such an argument system allows an efficient prover to prove multiple $NP$ statements, with size smaller than the combined witness length. We provide the first construction of such an argument system for $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 . 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 arguments Fiat-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},
      url = {https://eprint.iacr.org/2021/807}
}