International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Non-Interactive Batch Arguments for NP from Standard Assumptions

Arka Rai Choudhuri , Johns Hopkins University
Abhishek Jain , Johns Hopkins University
Zhengzhong Jin , Johns Hopkins University
Search ePrint
Search Google
Presentation: Slides
Conference: CRYPTO 2021
Abstract: We study the problem of designing *non-interactive batch arguments* for NP. Such an argument system allows an efficient prover to prove multiple $\npol$ statements, with size much 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-falsifiable 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 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.
Video from CRYPTO 2021
  title={Non-Interactive Batch Arguments for NP from Standard Assumptions},
  author={Arka Rai Choudhuri and Abhishek Jain and Zhengzhong Jin},