Paper 2023/754

Batch Proofs are Statistically Hiding

Abstract

Batch proofs are proof systems that convince a verifier that $$, for some $$ language $$, with communication that is much shorter than sending the $$ 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 $$, the class of *unique-witness* $$ languages. In the case of computational soundness (where both honest and dishonest provers are efficient), *non-interactive* solutions are now known for all of $$, assuming standard lattice or group assumptions. We exhibit the first negative results regarding the existence of batch proofs and arguments: - Statistically sound batch proofs for $$ imply that $$ has a statistically witness indistinguishable ($$) proof, with inverse polynomial $$ error, and a non-uniform honest prover. The implication is unconditional for obtaining honest-verifier $$ or for obtaining full-fledged $$ from public-coin protocols, whereas for private-coin protocols full-fledged $$ is obtained assuming one-way functions. This poses a barrier for achieving batch proofs beyond $$ (where witness indistinguishability is trivial). In particular, assuming that $$ does not have $$ proofs, batch proofs for all of $$ do not exist. - Computationally sound batch proofs (a.k.a batch arguments or $$s) for $$, together with one-way functions, imply statistical zero-knowledge ($$) arguments for $$ with roughly the same number of rounds, an inverse polynomial zero-knowledge error, and non-uniform honest prover. Thus, constant-round interactive $$s from one-way functions would yield constant-round $$ arguments from one-way functions. This would be surprising as $$ arguments are currently only known assuming constant-round statistically-hiding commitments. We further prove new positive implications of non-interactive batch arguments to non-interactive zero knowledge arguments (with explicit uniform prover and verifier): - Non-interactive $$s for $$, together with one-way functions, imply non-interactive computational zero-knowledge arguments for $$. Assuming also dual-mode commitments, the zero knowledge can be made statistical. Both our negative and positive results stem from a new framework showing how to transform a batch protocol for a language $$ into an $$ protocol for $$.

Note: Added a new result: NIBARG and OWF implies NICZKA.