Batch Proofs Are Statistically Hiding

Batch proofs are proof systems that convince a verifier that x1, . . . , xt P 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.

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

Computational Soundness: the existence of batch arguments (BARGs) 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 BARGs 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).

Non-interactive: the existence of non-interactive BARGs for NP and one-way functions, implies noninteractive statistical zero-knowledge arguments (NISZKA) for NP, with negligible soundness error, inverse polynomial zero-knowledge error, and non-uniform honest prover. Assuming also lossy publickey encryption, the statistical zero-knowledge error can be made negligible. We further show that BARGs 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.