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 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), noninteractive 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 statisticallysound batch proof for $L$ implies that $L$ has a statistically witness indistinguishable ($SWI$) proof, with inverse polynomial $SWI$ error, and a nonuniform honest prover. The implication is unconditional for publiccoin protocols and relies on oneway functions in the privatecoin 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 oneway functions, implies the existence of statistical zeroknowledge ($SZK$) arguments for $NP$ with roughly the same number of rounds, an inverse polynomial zeroknowledge error, and nonuniform honest prover. Thus, constantround interactive $BARG$s from oneway functions would yield constantround $SZK$ arguments from oneway functions. This would be surprising as $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 $BARG$s for $NP$ and oneway functions, implies noninteractive statistical zeroknowledge arguments ($NISZKA$) for $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. 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$.
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
 20230526: revised
 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} }