Batch Proofs are Statistically Hiding

Oded's comments

I find the title a bit confusing and potentially misleading, since one may misinterpret `hiding' as referring to the notion of witness hiding, which is not what the authors mean. In my opinion, a title like Batch Proofs imply Witness Indistinguishability (or Batch Proofs and Witness Indistinguishability) would have better captured the contents of this work.

In any case, I find the first result very intersting. As noted in the abstract, one of the main ingrediants in the celebrated construction of doublly-efficient interactive proofs for space bounded computations is the construction of (public-coin) batch proofs for any set in UP. The original proof makes an essential use of the unique witness feature, but a natural question raised by it is whether this is an artifact of the techniques or is an inherent limitation.

I read the first result of the current paper as suggesting that the foregoing restriction (to UP) is essentially an inherent one. This is, of course, based on the conjecture that NP-complete sets are unlikely to have (honest-verifier) statistically witness indistinguishable (SWI) proof systems. Indeed, when taking a complexity theoretic perspective (unlike when taking a cryptographic perspective), honest-verifier results are good enough.

The authors warn that one should not deduce from SZK to SWI, and yet the conjecture that SWI cannot cover all of NP sounds correct to me. I agree with the authors that SWI deserves some serious study and view the fact that such a study was not conducted so far as a typical neglect of TOC... (Indeed, this triggers my usual reflections on why some questions are extensively studied while others are ignore or neglected; I guess that in the current case falling betwen cryptography and complexity theory (equiv., far from the center of mass of either) may be part of the reason.)

Section 1.3 does a very good job in sketching the ideas that underlies the main proofs. I highly recommend reading it.

The original abstract [with a couple of clarifications]

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), [public coin] 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.

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 $SWI$ error, and a non-uniform honest prover. The implication is unconditional for public-coin protocols and relies on one-way functions in the private-coin case. [This refers to getting full-fledged SWI; the results for honest-verifier SWI are unconditional.]
   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.
2. Computational Soundness: the existence of batch arguments ($BARG$s) 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 $BARG$s 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).
3. Non-interactive: the existence of non-interactive $BARG$s 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 error can be made negligible. We further show that $BARG$s satisfying a notion of honest somewhere extractability imply lossy public key encryption.

See ECCC TR23-077.