Batch proofs are (possibly interactive) 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. Batch proofs have been studied in various settings in recent years. In the case of statistical soundness (where the cheating prover is unbounded but honest prover is efficient), interactive solutions are known for any UP language. 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 present a connection between batch proofs and Statistically Witness-Indistinguishable (SWI) proofs with various interesting implications. On the negative side, we obtain some evidence against the existence of statistically sound batch proofs for NP-hard problems. On the other hand, we show that computationally sound batch proofs for NP, together with one-way functions, can be used to construct various non-trivial zero-knowledge argument systems for NP.

Based on work with Nir Bitansky, Chethan Kamath, Omer Paneth, and Ron D. Rothblum. The paper may be found here: link