Batch proofs are proof systems that convince a verifier that x_1,…,x_t are 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 the honest prover is efficient given the witnesses), interactive batch proofs are known for UP, the class of unique witness NP languages. In the case of computational soundness (a.k.a. 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 non- uniform honest prover. The implication is unconditional for obtaining honest-verifier SWI or for obtaining full-fledged SWI from public-coin protocols, whereas for private-coin protocols full-fledged SWI is obtained assuming one-way functions. 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.

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 non- interactive statistical zero-knowledge arguments (NISZKA) for NP, with negligible soundness error, inverse polynomial zero-knowledge error, and non-uniform honest prover. Assuming also lossy public-key encryption, the statistical zero-knowledge erroour results stem from a common framework showing how to transform batch protocol for a language L into an SWI protocol for L.

(Based on work with Nir Bitansky, Omer Paneth, Prashant Nalini Vasudevan and Ron D. Rothblum)