[Resource Topic] 2021/807: Non-Interactive Batch Arguments for NP from Standard Assumptions

Welcome to the resource topic for 2021/807

Non-Interactive Batch Arguments for NP from Standard Assumptions

Authors: Arka Rai Choudhuri, Abhishek Jain, Zhengzhong Jin


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.

ePrint: https://eprint.iacr.org/2021/807

Talk: https://www.youtube.com/watch?v=VAmJjkBygPU

Slides: https://iacr.org/submit/files/slides/2021/crypto/crypto2021/312/slides.pdf

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .