Cryptology ePrint Archive: Report 2021/807

Non-Interactive Batch Arguments for NP from Standard Assumptions

Arka Rai Choudhuri and 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.

Category / Keywords: foundations / Batch arguments, Fiat-Shamir Transformation

Original Publication (with minor differences): IACR-CRYPTO-2021

Date: received 14 Jun 2021, last revised 15 Jun 2021

Contact author: achoud at cs jhu edu, abhishek at cs jhu edu, zjin12 at jhu edu

Available format(s): PDF | BibTeX Citation

Version: 20210616:132855 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]