Paper 2023/695

Non-Interactive Zero-Knowledge from Non-Interactive Batch Arguments

Jeffrey Champion, The University of Texas at Austin
David J. Wu, The University of Texas at Austin

Zero-knowledge and succinctness are two important properties that arise in the study of non-interactive arguments. Previously, Kitagawa et al. (TCC 2020) showed how to obtain a non-interactive zero-knowledge (NIZK) argument for NP from a succinct non-interactive argument (SNARG) for NP. In particular, their work demonstrates how to leverage the succinctness property from an argument system and transform it into a zero-knowledge property. In this work, we study a similar question of leveraging succinctness for zero-knowledge. Our starting point is a batch argument for NP, a primitive that allows a prover to convince a verifier of $T$ NP statements $x_1, \ldots, x_T$ with a proof whose size scales sublinearly with $T$. Unlike SNARGs for NP, batch arguments for NP can be built from group-based assumptions in both pairing and pairing-free groups and from lattice-based assumptions. The challenge with batch arguments is that the proof size is only amortized over the number of instances, but can still encode full information about the witness to a small number of instances. We show how to combine a batch argument for NP with a local pseudorandom generator (i.e., a pseudorandom generator where each output bit only depends on a small number of input bits) and a dual-mode commitment scheme to obtain a NIZK for NP. Our work provides a new generic approach of realizing zero-knowledge from succinctness and highlights a new connection between succinctness and zero-knowledge.

Available format(s)
Publication info
A minor revision of an IACR publication in CRYPTO 2023
zero-knowledgeNIZKbatch argumentsBARG
Contact author(s)
jchampion @ utexas edu
dwu4 @ cs utexas edu
2023-08-05: revised
2023-05-16: received
See all versions
Short URL
Creative Commons Attribution


      author = {Jeffrey Champion and David J. Wu},
      title = {Non-Interactive Zero-Knowledge from Non-Interactive Batch Arguments},
      howpublished = {Cryptology ePrint Archive, Paper 2023/695},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.