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 *uniquewitness* $\mathsf{NP}$ languages. In the case of computational soundness (where both honest and dishonest provers are efficient), *noninteractive* solutions are now known for all of $\mathsf{NP}$, assuming standard lattice or group assumptions. We exhibit the first negative results regarding the existence of batch proofs and arguments:  Statistically sound batch proofs for $\mathcal{L}$ imply 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.  Computationally sound batch proofs (a.k.a batch arguments or $\mathsf{BARG}$s) for $\mathsf{NP}$, together with oneway functions, imply 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. We further prove new positive implications of noninteractive batch arguments to noninteractive zero knowledge arguments (with explicit uniform prover and verifier):  Noninteractive $\mathsf{BARG}$s for $\mathsf{NP}$, together with oneway functions, imply noninteractive computational zeroknowledge arguments for $\mathsf{NP}$. Assuming also dualmode commitments, the zero knowledge can be made statistical. Both our negative and positive results stem from a new framework showing how to transform a batch protocol for a language $\mathcal{L}$ into an $\mathsf{SWI}$ protocol for $\mathcal{L}$.
Note: Added a new result: NIBARG and OWF implies NICZKA.
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
 20231204: last of 4 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}, url = {https://eprint.iacr.org/2023/754} }