[Resource Topic] 2023/754: Batch Proofs are Statistically Hiding

Resource Foundations
#1

Welcome to the resource topic for 2023/754

Title:
Batch Proofs are Statistically Hiding

Authors: Nir Bitansky, Chethan Kamath, Omer Paneth, Ron Rothblum, Prashant Nalina Vasudevan

Abstract:

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), 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 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.

  1. 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).

  2. 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.

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 L.

ePrint: https://eprint.iacr.org/2023/754

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .