Paper 2023/754

Batch Proofs are Statistically Hiding

Nir Bitansky, Tel Aviv University
Chethan Kamath, Tel Aviv University
Omer Paneth, Tel Aviv University
Ron Rothblum, Technion – Israel Institute of Technology
Prashant Nalini Vasudevan, National University of Singapore

Batch proofs are proof systems that convince a verifier that $x_1,\dots, x_t \in L$, for some $NP$ language $L$, with communication that is much shorter than sending the $t$ witnesses. In the case of statistical soundness (where the cheating prover is unbounded but honest prover is efficient), interactive batch proofs are known for $UP$, the class of unique witness $NP$ languages. In the case of computational soundness (aka arguments, where both honest and dishonest provers are efficient), non-interactive solutions are now known for all of $NP$, assuming standard cryptographic assumptions. We study the necessary conditions for the existence of batch proofs in these two settings. Our main results are as follows. 1. Statistical Soundness: the existence of a statistically-sound batch proof for $L$ implies that $L$ has a statistically witness indistinguishable ($SWI$) proof, with inverse polynomial $SWI$ error, and a non-uniform honest prover. The implication is unconditional for public-coin protocols and relies on one-way functions in the private-coin case. This poses a barrier for achieving batch proofs beyond $UP$ (where witness indistinguishability is trivial). In particular, assuming that $NP$ does not have $SWI$ proofs, batch proofs for all of $NP$ do not exist. This motivates further study of the complexity class $SWI$, which, in contrast to the related class $SZK$, has been largely left unexplored. 2. Computational Soundness: the existence of batch arguments ($BARG$s) for $NP$, together with one-way functions, implies the existence of statistical zero-knowledge ($SZK$) arguments for $NP$ with roughly the same number of rounds, an inverse polynomial zero-knowledge error, and non-uniform honest prover. Thus, constant-round interactive $BARG$s from one-way functions would yield constant-round $SZK$ arguments from one-way functions. This would be surprising as $SZK$ arguments are currently only known assuming constant-round statistically-hiding commitments (which in turn are unlikely to follow from one-way functions). 3. Non-interactive: the existence of non-interactive $BARG$s for $NP$ and one-way functions, implies non-interactive statistical zero-knowledge arguments ($NISZKA$) for $NP$, with negligible soundness error, inverse polynomial zero-knowledge error, and non-uniform honest prover. Assuming also lossy public-key encryption, the statistical zero-knowledge error can be made negligible. We further show that $BARG$s satisfying a notion of honest somewhere extractability imply lossy public key encryption. All of our results stem from a common framework showing how to transform a batch protocol for a language $L$ into an $SWI$ protocol for $L$.

Available format(s)
Publication info
Batch ProofsWitness IndistinguishabilityZero-Knowledge
Contact author(s)
nirbitan @ tau ac il
ckamath @ protonmail com
omerpa @ tauex tau ac il
rothblum @ cs technion ac il
prashant @ comp nus edu sg
2023-05-26: revised
2023-05-25: received
See all versions
Short URL
No rights reserved


      author = {Nir Bitansky and Chethan Kamath and Omer Paneth and Ron Rothblum and Prashant Nalini Vasudevan},
      title = {Batch Proofs are Statistically Hiding},
      howpublished = {Cryptology ePrint Archive, Paper 2023/754},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.