Welcome to the resource topic for 2023/754
Title:
Batch Proofs are Statistically Hiding
Authors: Nir Bitansky, Chethan Kamath, Omer Paneth, Ron Rothblum, Prashant Nalina Vasudevan
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.
 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.

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).

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.
ePrint: https://eprint.iacr.org/2023/754
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .