Paper 2023/754
Batch Proofs are Statistically Hiding
Abstract
Batch proofs are proof systems that convince a verifier that $x_1,\dots,x_t \in \mathcal{L}$, for some $\mathsf{NP}$ language $\mathcal{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 $\mathsf{UP}$, the class of unique witness $\mathsf{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 $\mathsf{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 $\mathcal{L}$ implies that $\mathcal{L}$ has a statistically witness indistinguishable ($\mathsf{SWI}$) proof, with inverse polynomial $\mathsf{SWI}$ error, and a non-uniform honest prover. The implication is unconditional for obtaining honest-verifier $\mathsf{SWI}$ or for obtaining full-fledged $\mathsf{SWI}$ from public-coin protocols, whereas for private-coin protocols full-fledged $\mathsf{SWI}$ is obtained assuming one-way functions. This poses a barrier for achieving batch proofs beyond $\mathsf{UP}$ (where witness indistinguishability is trivial). In particular, assuming that $\mathsf{NP}$ does not have $\mathsf{SWI}$ proofs, batch proofs for all of $\mathsf{NP}$ do not exist. 2. Computational Soundness: the existence of batch arguments ($\mathsf{BARG}$s) for $\mathsf{NP}$, together with one-way functions, implies the existence of statistical zero-knowledge ($\mathsf{SZK}$) arguments for $\mathsf{NP}$ with roughly the same number of rounds, an inverse polynomial zero-knowledge error, and non-uniform honest prover. Thus, constant-round interactive $\mathsf{BARG}$s from one-way functions would yield constant-round $\mathsf{SZK}$ arguments from one-way functions. This would be surprising as $\mathsf{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 $\mathsf{BARG}$s for $\mathsf{NP}$ and one-way functions, implies non-interactive statistical zero-knowledge arguments ($\mathsf{NISZKA}$) for $\mathsf{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 and the honest prover can be made uniform. All of our results stem from a common framework showing how to transform a batch protocol for a language $\mathcal{L}$ into an $\mathsf{SWI}$ protocol for $\mathcal{L}$.
Note: Revised statement and proof of Theorems 3.10 and 3.14
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Preprint.
- Keywords
- Batch ProofsWitness IndistinguishabilityZero-Knowledge
- Contact author(s)
-
nirbitan @ tau ac il
ckamath @ protonmail com
omerpa @ tauex tau ac il
rothblum @ cs technion ac il
prashant @ comp nus edu sg - History
- 2023-07-25: last of 3 revisions
- 2023-05-25: received
- See all versions
- Short URL
- https://ia.cr/2023/754
- License
-
CC0
BibTeX
@misc{cryptoeprint:2023/754, author = {Nir Bitansky and Chethan Kamath and Omer Paneth and Ron Rothblum and Prashant Nalini Vasudevan}, title = {Batch Proofs are Statistically Hiding}, howpublished = {Cryptology ePrint Archive, Paper 2023/754}, year = {2023}, note = {\url{https://eprint.iacr.org/2023/754}}, url = {https://eprint.iacr.org/2023/754} }