Abstract
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 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 statistically-sound batch proof for L implies that L has a Statistically Witness Indistinguishable (SWI) proof, with inverse polynomial soundness and SWI errors, and a non-uniform honest prover. In particular, under the assumption that NP does not have such SWI proofs, then batch proofs for all of NP do not exist.
2. 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, and an inverse polynomial zero-knowledge error and non-uniform honest prover. Thus, constructing constant-round interactive BARGs from one-way functions would yield constant-round SZK arguments, which are currently only known assuming constant-round statistically-hiding commitments.
3. Non-interactive: the existence of non-interactive BARGs for NP, satisfying a notion of soundness called ``somewhere extractability'' (achieved by recent constructions), imply non-interactive statistical zero-knowledge arguments (NISZKA) for NP, with negligible zero-knowledge and soundness errors and a non-uniform honest prover.
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 a single instance of L.
Based on work with Nir Bitansky, Chethan Kamath, Omer Paneth, and Ron D. Rothblum