Paper 2023/754
Batch Proofs are Statistically Hiding
Abstract
Batch proofs are proof systems that convince a verifier that $x_1,\dots,x_t \in \mathcal{L}$, for some $\mathsf{NP}$ language $\mathcal{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 the honest prover is efficient given the witnesses), interactive batch proofs are known for $\mathsf{UP}$, the class of unique witness $\mathsf{NP}$ languages. In the case of computational soundness (a.k.a. arguments, where both honest and dishonest provers are efficient), noninteractive solutions are now known for all of $\mathsf{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 statisticallysound batch proof for $\mathcal{L}$ implies that $\mathcal{L}$ has a statistically witness indistinguishable ($\mathsf{SWI}$) proof, with inverse polynomial $\mathsf{SWI}$ error, and a nonuniform honest prover. The implication is unconditional for obtaining honestverifier $\mathsf{SWI}$ or for obtaining fullfledged $\mathsf{SWI}$ from publiccoin protocols, whereas for privatecoin protocols fullfledged $\mathsf{SWI}$ is obtained assuming oneway functions. This poses a barrier for achieving batch proofs beyond $\mathsf{UP}$ (where witness indistinguishability is trivial). In particular, assuming that $\mathsf{NP}$ does not have $\mathsf{SWI}$ proofs, batch proofs for all of $\mathsf{NP}$ do not exist. 2. Computational Soundness: the existence of batch arguments ($\mathsf{BARG}$s) for $\mathsf{NP}$, together with oneway functions, implies the existence of statistical zeroknowledge ($\mathsf{SZK}$) arguments for $\mathsf{NP}$ with roughly the same number of rounds, an inverse polynomial zeroknowledge error, and nonuniform honest prover. Thus, constantround interactive $\mathsf{BARG}$s from oneway functions would yield constantround $\mathsf{SZK}$ arguments from oneway functions. This would be surprising as $\mathsf{SZK}$ arguments are currently only known assuming constantround statisticallyhiding commitments (which in turn are unlikely to follow from oneway functions). 3. Noninteractive: the existence of noninteractive $\mathsf{BARG}$s for $\mathsf{NP}$ and oneway functions, implies noninteractive statistical zeroknowledge arguments ($\mathsf{NISZKA}$) for $\mathsf{NP}$, with negligible soundness error, inverse polynomial zeroknowledge error, and nonuniform honest prover. Assuming also lossy publickey encryption, the statistical zeroknowledge error can be made negligible and the honest prover can be made uniform. All of our results stem from a common framework showing how to transform a batch protocol for a language $\mathcal{L}$ into an $\mathsf{SWI}$ protocol for $\mathcal{L}$.
Note: Revised statement and proof of Theorems 3.10 and 3.14
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Preprint.
 Keywords
 Batch ProofsWitness IndistinguishabilityZeroKnowledge
 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  History
 20230725: last of 3 revisions
 20230525: received
 See all versions
 Short URL
 https://ia.cr/2023/754
 License

CC0
BibTeX
@misc{cryptoeprint:2023/754, 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{https://eprint.iacr.org/2023/754}}, url = {https://eprint.iacr.org/2023/754} }